The Core Conjecture of Hilton and Zhao II: a Proof

Abstract

A simple graph $G$ with maximum degree $\Delta$ is overfull if $|E(G)|>\Delta \lfloor |V(G)|/2\rfloor$. The core of $G$, denoted $G_{\Delta }$, is the subgraph of $G$ induced by its vertices of degree $\Delta$. Clearly, the chromatic index of $G$ equals $\Delta +1$ if $G$ is overfull. Conversely, Hilton and Zhao in 1996 conjectured that if $G$ is a simple connected graph with $\Delta \ge 3$ and $\Delta (G_{\Delta })\le 2$, then ${\chi }^{\prime }(G)=\Delta +1$ implies that $G$ is overfull or $G=P^{\ast }$, where $P^{\ast }$ is obtained from the Petersen graph by deleting a vertex. Cariolaro and Cariolaro settled the base case $\Delta =3$ in 2003, and Cranston and Rabern proved the next case $\Delta =4$ in 2019. In this paper, we give a proof of this conjecture for all $\Delta \ge 4$.

This is the second split of arXiv:2004.00734, and is the sequel to arXiv:2108.03549. arXiv admin note: substantial text overlap with arXiv:2004.00734

References in corpus (1)

• Pseudo-multifan and Lollipop