2022/05/17 by Shan, Songling · 1 citation
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2205.08564
Let G be a simple graph with maximum degree Δ(G). A subgraph H of G is overfull if |E(H)|>Δ(G)\lfloor (1)/(2)|V(H)| \rfloor. Chetwynd and Hilton in 1986 conjectured that a graph G with Δ(G)>(1)/(3)|V(G)| has chromatic index Δ(G) if and only if G contains no overfull subgraph. Let 0<ε <1 and G be a large graph on n vertices with minimum degree at least (1)/(2)(1+ε)n. It was shown that the conjecture holds for G if n is even. In this paper, the same result is proved if n is odd. As far as we know, this is the first result on the conjecture for graphs of odd order and with a minimum degree constraint.