{"id":"arxiv/2607.10947","url":"https://arxiv.org/abs/2607.10947","tags":["math.CO"],"score":0,"title":"Edge-chromatic $4$-critical graphs and Overfull Conjecture for graphs with maximum degree $4$","domain":"math.CO","source":"arxiv","authors":["Chunhui Ge","Gregory Gutin","Xuli Qi"],"reviews":0,"subject":"math.CO","summary":"Let $G$ be a simple graph with maximum degree $Δ(G)$ and chromatic index $χ'(G)$. A graph $G$ is called edge-chromatic $Δ$-critical if $χ'(G)=Δ(G)+1$ and $χ'(H) Δ(G)\\lfloor |V(G)|/2\\rfloor$. In 1986, Chetwynd and Hilton proposed the influential Overfull Conjecture: If $G$ is a simple graph with $Δ(G)>\\frac{|V(G)|}{3}$, then $G$ is a Class $2$ graph if and only if $G$ contains an overfull subgraph $H$ with $Δ(H)=Δ(G)$. Motivated by the structural analysis for $4$-critical graphs (SIAM J. Discrete Math. 2019), we show more properties in this paper, especially four new forbidden configurations…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-07-12","reactions":{}}