Vizing's 2-factor Conjecture Involving Toughness and Maximum Degree Conditions

Abstract

Let $G$ be a simple graph, 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$. We say $G$ is $\Delta$-critical if ${\chi }^{\prime }(G)=\Delta +1$ and ${\chi }^{\prime }(H)<{\chi }^{\prime }(G)$ for every proper subgraph $H$ of $G$. In 1968, Vizing conjectured that if $G$ is a $\Delta$-critical graph, then $G$ has a 2-factor. Let $G$ be an $n$-vertex $\Delta$-critical graph. It was proved that if $\Delta (G)\ge n/2$, then $G$ has a 2-factor; and that if $\Delta (G)\ge 2n/3+12$, then $G$ has a hamiltonian cycle, and thus a 2-factor. It is well known that every 2-tough graph with at least three vertices has a 2-factor. We investigate the existence of a 2-factor in a $\Delta$-critical graph under "moderate" given toughness and maximum degree conditions. In particular, we show that if $G$ is an $n$-vertex $\Delta$-critical graph with toughness at least 3/2 and with maximum degree at least $n/3$, then $G$ has a 2-factor. In addition, we develop new techniques in proving the existence of 2-factors in graphs.

arXiv admin note: text overlap with arXiv:1404.6299