Towards the Overfull Conjecture II

Abstract

Let $G$ be a simple graph with maximum degree $\hat{I}”(G)$. A subgraph $H\subseteq G$ is $\hat{I}”(G)$-overfull if $|E(H)|>\hat{I}”(G)\lfloor |V(H)|/2\rfloor$. In any edge coloring of $G$, each color class restricted to $H$ is a matching of size at most $\lfloor |V(H)|/2\rfloor$. Thus, if $G$ contains a $\hat{I}”(G)$-overfull subgraph, then $G$ cannot be edge-colored with only $\hat{I}”(G)$ colors. By Vizing's Theorem, $\ddot{I}{‡}^{\prime }(G)\le \hat{I}”(G)+1$, and hence $G$ is class $2$. In 1986, Chetwynd and Hilton conjectured that whenever $\hat{I}”(G)>|V(G)|/3$, the converse also holds: every class $2$ graph $G$ contains a $\hat{I}”(G)$-overfull subgraph. This statement, commonly known as the Overfull Conjecture, is one of the most influential conjectures in graph edge coloring. It would imply a polynomial-time algorithm for determining the chromatic index of graphs $G$ with $\hat{I}”(G)>|V(G)|/3$, and would also imply several other longstanding conjectures in the area, including the Just-overfull Conjecture and the Vertex-splitting Conjecture. In previous work, the third author verified the conjecture for large graphs $G$ with maximum degree at least $13|V(G)|/14$. In this paper, we confirm the conjecture for robust expanders satisfying certain density constraints. As a consequence, for every $0<\epsilon <1$, the conjecture holds for all sufficiently large graphs $G$ with maximum degree at least $(1+\epsilon )|V(G)|/2$.