Vizing's 2-factor conjecture involving toughness and maximum degree conditions (Q2415079): Difference between revisions

Summary: Let \(G\) be a simple graph, and let \(\Delta(G)\) and \(\chi'(G)\) denote the maximum degree and chromatic index of \(G\), respectively. Vizing proved that \(\chi'(G)=\Delta(G)\) or \(\chi'(G)=\Delta(G)+1\). We say \(G\) is \(\Delta\)-critical if \(\chi'(G)=\Delta(G)+1\) and \(\chi'(H)<\chi'(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+13\), 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. We also construct a family of graphs that have order \(n\), maximum degree \(n-1\), toughness at least \(3/2\), but have no 2-factor. This implies that the \(\Delta\)-criticality in the result is needed. In addition, we develop new techniques in proving the existence of 2-factors in graphs.