The Hilton--Zhao Conjecture is True for Graphs with Maximum Degree 4
Daniel W. Cranston, Landon Rabern · SIAM Journal on Discrete Mathematics · 2019
A simple graph $G$ is overfull if ${|E(G)|}>\Delta\lfloor|V(G)|/2\rfloor$. By the pigeonhole principle, every overfull graph $G$ has $\chi'(G)>\Delta$. The 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'(G)>\Delta$, then $G_\Delta$ contains cycles. Hilton and Zhao conjectured that if $G$ is connected with $\Delta\ge 4$ and $G_\Delta$ has maximum degree 2, then $\chi'(G)>\Delta$ precisely when $G$ is overfull. We prove this conjecture for the case $\Delta=4$.