$Δ$-critical graphs with a vertex of degree 2

Let $G$ be a simple graph with maximum degree $Δ$. A classic result of Vizing shows that $χ'(G)$, the chromatic index of $G$, is either $Δ$ or $Δ+1$. We say $G$ is of \emph{Class 1} if $χ'(G)=Δ$, and is of \emph{Class 2} otherwise. A graph $G$ is \emph{$Δ$-critical} if $χ'(G)=Δ+1$ and $χ'(H)<Δ+1$ for every proper subgraph $H$ of $G$, and is \emph{overfull} if $|E(G)|>Δ\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 $Δ$-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 $Δ\ge \frac{n}{2}(\sqrt{7}-1)\approx 0.82n$. In this paper, we improve the bound on $Δ$ from $\frac{n}{2}(\sqrt{7}-1)$ to $0.75n$. Considering the structure of $Δ$-critical graphs with a vertex of degree 2, we also show that for an $n$-vertex $Δ$-critical graph with $Δ\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 $Δ$-critical graph with $Δ>n/3$, then $G$ contains an overfull subgraph $H$ with $Δ(H)=Δ$. Our proof techniques are new and might shed some light on attacking both of the conjectures when $Δ$ is large.

No reviews yet.

No comments yet.