The overfull conjecture on graphs of odd order and large minimum degree

Abstract

Let $G$ be a simple graph with maximum degree $\Delta (G)$. A subgraph $H$ of $G$ is overfull if $|E(H)|>\Delta (G)\lfloor \frac{1}{2}|V(H)|\rfloor$. Chetwynd and Hilton in 1986 conjectured that a graph $G$ with $\Delta (G)>\frac{1}{3}|V(G)|$ has chromatic index $\Delta (G)$ if and only if $G$ contains no overfull subgraph. Let $0<\epsilon <1$ and $G$ be a large graph on $n$ vertices with minimum degree at least $\frac{1}{2}(1+\epsilon )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.

arXiv commentarXiv admin note: substantial text overlap with arXiv:2105.05286, arXiv:2104.06253; text overlap with arXiv:1010.5192 by other authors