Vizing's 2-factor Conjecture Involving Large Maximum Degree

Abstract

Let $G$ be a connected simple graph of order $n$ and let $\Delta (G)$ and ${\chi }^{\prime }(G)$ denote the maximum degree and chromatic index of $G$, respectively. Vizing proved that ${\chi }^{\prime }(G)=\Delta (G)$ or $\Delta (G)+1$. Following this result, $G$ is called $\Delta$-critical if ${\chi }^{\prime }(G)=\Delta (G)+1$ and ${\chi }^{\prime }(G-e)=\Delta (G)$ for every $e\in E(G)$. In 1968, Vizing conjectured that if $G$ is an $n$-vertex $\Delta$-critical graph, then the independence number $\alpha (G)\le n/2$. Furthermore, he conjectured that, in fact, $G$ has a 2-factor. Luo and Zhao showed that if $G$ is an $n$-vertex $\Delta$-critical graph with $\Delta (G)\ge n/2$, then $\alpha (G)\le n/2$. More recently, they showed that if $G$ is an $n$-vertex $\Delta$-critical graph with $\Delta (G)\ge 6n/7$, then $G$ has a hamiltonian cycle, and so $G$ has a 2-factor. In this paper, we show that if $G$ is an $n$-vertex $\Delta$-critical graph with $\Delta (G)\ge n/2$, then $G$ has a 2-factor.