2026/07/31 by Chunhui Ge, Gregory Gutin, Xuli Qi
Mathematics · #math.CO
arxiv created 2026/07/31 · arxiv updated 2026/08/03
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) for every proper subgraph H of G, and G is overfull if |E(G)|>Δ(G)\lfloor |V(G)|/2\rfloor. In 1986, Chetwynd and Hilton proposed the influential Overfull Conjecture: If G is a simple graph with Δ(G)>(|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 in any 4-critical graph, and provide a new structural proof of Overfull Conjecture for graphs with maximum degree 4.