A simple graph $G$ with maximum degree $Delta$ is overfull if $|E(G)|>Delta lfloor |V(G)|/2rfloor$. 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 $Deltage 3$ and $Delta(G_Delta)le 2$, then $chi(G)=Delta+1$ implies that $G$ is overfull or $G=P^*$, where $P^*$ 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 $Deltage 4$.
تحميل البحث