Vizing's 2‐Factor Conjecture Involving Large Maximum Degree
Guantao Chen, Songling Shan · Journal of Graph Theory · 2017
Abstract Let G be an n‐vertex simple graph, and let and denote the maximum degree and chromatic index of G, respectively. Vizing proved that or . Define G to be Δ‐critical if and for every proper subgraph H of G. In 1965, Vizing conjectured that if G is an n‐vertex Δ‐critical graph, then G has a 2‐factor. Luo and Zhao showed if G is an n‐vertex Δ‐critical graph with , then G has a hamiltonian cycle, and so G has a 2‐factor. In this article, we show that if G is an n‐vertex Δ‐critical graph with , then G has a 2‐factor.