$\Delta$-critical graphs with a vertex of degree 2

Abstract

Let $G$ be a simple graph with maximum degree $\Delta$. A classic result of Vizing shows that ${\chi }^{\prime }(G)$, the chromatic index of $G$, is either $\Delta$ or $\Delta +1$. We say $G$ is of \emph{Class 1} if ${\chi }^{\prime }(G)=\Delta$, and is of \emph{Class 2} otherwise. A graph $G$ is \emph{$\Delta$-critical} if ${\chi }^{\prime }(G)=\Delta +1$ and ${\chi }^{\prime }(H)<\Delta +1$ for every proper subgraph $H$ of $G$, and is \emph{overfull} if $|E(G)|>\Delta \lfloor (|V(G)|-1)/2\rfloor$. Clearly, overfull graphs are Class 2. Hilton and Zhao in 1997 conjectured that if $G$ is obtained from an $n$-vertex $\Delta$-regular Class 1 graph with maximum degree greater than $n/3$ by splitting a vertex, then being overfull is the only reason for $G$ to be Class 2. This conjecture was only confirmed when $\Delta \ge \frac{n}{2}(\sqrt{7}-1)\approx 0.82n$. In this paper, we improve the bound on $\Delta$ from $\frac{n}{2}(\sqrt{7}-1)$ to $0.75n$. Considering the structure of $\Delta$-critical graphs with a vertex of degree 2, we also show that for an $n$-vertex $\Delta$-critical graph with $\Delta \ge \frac{3n}{4}$, if it contains a vertex of degree 2, then it is overfull. We actually obtain a more general form of this result, which partially supports the overfull conjecture of Chetwynd and Hilton from 1986, which states that if $G$ is an $n$-vertex $\Delta$-critical graph with $\Delta >n/3$, then $G$ contains an overfull subgraph $H$ with $\Delta (H)=\Delta$. Our proof techniques are new and might shed some light on attacking both of the conjectures when $\Delta$ is large.

arXiv admin note: text overlap with arXiv:2004.00734