Let $G$ be a simple graph with maximum degree $Delta$. We call $G$ emph{overfull} if $|E(G)|>Delta lfloor |V(G)|/2rfloor$. The emph{core} of $G$, denoted $G_{Delta}$, is the subgraph of $G$ induced by its vertices of degree $Delta$. A classic result of Vizing shows that $chi(G)$, the chromatic index of $G$, is either $Delta$ or $Delta+1$. It is NP-complete to determine the chromatic index for a general graph. However, if $G$ is overfull then $chi(G)=Delta+1$. 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$ if and only if $G$ is overfull or $G=P^*$, where $P^*$ is obtained from the Petersen graph by deleting a vertex. This conjecture, if true, implies an easy approach for calculating $chi(G)$ for graphs $G$ satisfying the conditions. The progress on the conjecture has been slow: it was only confirmed for $Delta=3,4$, respectively, in 2003 and 2017. In this paper, we confirm this conjecture for all $Deltage 4$.
تحميل البحث