Sharpening an ore-type version of the Corrádi-Hajnal theorem (Q1688267)

In this long paper, the authors studied an Ore-type version of the Corrádi-Hajnal theorem and resolved the difficult case when \(|G|=3k\). \textit{K. Corradi} and \textit{A. Hajnal} [Acta Math. Acad. Sci. Hung. 14, 423--439 (1963; Zbl 0118.19001)] proved that for all \(k \geq 1\) and \(n \geq 3 k\), every (simple) graph \(G\) on \(n\) vertices with minimum degree \(\delta(G) \geq 2 k\) contains \(k\) disjoint cycles. The degree bound is sharp. \textit{H. Enomoto} [Combinatorica 18, No. 4, 487--492 (1998; Zbl 0924.05041)] and \textit{H. Wang} [Discrete Math. 205, No. 1--3, 183--190 (1999; Zbl 0936.05063)] proved the refinement of the Corrádi-Hajnal theorem: For all \(k \geq 1\) and \(n \geq 3 k\), every graph \(G\) on \(n\) vertices contains \(k\) disjoint cycles, provided that \(d(x)+d(y) \geq 4 k-1\) for all distinct nonadjacent vertices \(x\), \(y\). Recently, it was refined for \(k \geq 3\) and \(n \geq 3 k+1\): If \(G\) is a graph on \(n\) vertices such that \(d(x)+d(y) \geq 4 k-3\) for all distinct nonadjacent vertices \(x\), \(y,\) then \(G\) has \(k\) vertex-disjoint cycles if and only if the independence number \(\alpha(G) \leq n-2 k\) and \(G\) is not one of two small exceptions in the case \(k=3\). But the difficult case, \(n=3 k,\) was not handled. In this paper, the authors resolved this difficult case using an equitable \(k\)-coloring and obtain the full picture of extremal graphs for the Ore-type version of the Corrádi-Hajnal theorem. Since any \(k\) disjoint cycles in a \(3 k\)-vertex graph \(G\) must be 3-cycles, the existence of such \(k\) cycles is equivalent to the existence of an equitable \(k\)-coloring of the complement of \(G\). This result can be also considered as an Ore-type version of a partial case of the Chen-Lih-Wu conjecture on equitable colorings.