The Hilton--Zhao Conjecture is True for Graphs with Maximum Degree 4

Abstract

A simple graph $G$ is \emph{overfull} if $|E(G)|>\Delta \lfloor |V(G)|/2\rfloor$. By the pigeonhole principle, every overfull graph $G$ has ${\chi }^{\prime }(G)>\Delta$. The \emph{core} of a graph, denoted $G_{\Delta }$, is the subgraph induced by its vertices of degree $\Delta$. Vizing's Adjacency Lemma implies that if ${\chi }^{\prime }(G)>\Delta$, then $G_{\Delta }$ contains cycles. Hilton and Zhao conjectured that if $G_{\Delta }$ has maximum degree 2 and $\Delta \ge 4$, then ${\chi }^{\prime }(G)>\Delta$ precisely when $G$ is overfull. We prove this conjecture for the case $\Delta =4$.

13 pages, 9 figures; this version incorporates reviewer feedback and corrects a few errors; to appear in SIAM J. Discrete Math