Towards the Overfull Conjecture II

Let $G$ be a simple graph with maximum degree $\Delta(G)$.

A subgraph $H\subseteq G$ is $\Delta(G)$-overfull if $|E(H)|>\Delta(G)\left\lfloor |V(H)|/2\right\rfloor$.

In any edge coloring of $G$, each color class restricted to $H$ is a matching of size at most $\left\lfloor |V(H)|/2\right\rfloor$.

Thus, if $G$ contains a $\Delta(G)$-overfull subgraph, then $G$ cannot be edge-colored with only $\Delta(G)$ colors.

By Vizing's Theorem, $\chi'(G)\le \Delta(G)+1$, and hence $G$ is class $2$.

In 1986, Chetwynd and Hilton conjectured that whenever $\Delta(G)>|V(G)|/3$, the converse also holds: every class $2$ graph $G$ contains a $\Delta(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 $\Delta(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<\varepsilon<1$, the conjecture holds for all sufficiently large graphs $G$ with maximum degree at least $(1+\varepsilon)|V(G)|/2$.