Strengthening Theorems of Dirac and Erdos on Disjoint Cycles

Let k >= 3 be an integer, H-k(G) be the set of vertices of degree at least 2k in a graph G, and L-k(G) be the set of vertices of degree at most 2k - 2 in G. In 1963, Dirac and Erdos proved that G contains k (vertex) disjoint cycles whenever |H-k(G)| - |L-k(G)| >= k(2) + 2k - 4. The main result of this article is that for k >= 2, every graph G with |V(G)| >= 3k containing at most t disjoint triangles and with |H-k(G)| - |L-k(G)| >= 2k + t contains k disjoint cycles. This yields that if k >= 2 and |H-k(G)| - |L-k(G)| >= 3k, then G contains k disjoint cycles. This generalizes the Corradi-Hajnal Theorem, which states that every graph G with H-k(G) = V(G) and |H-k(G)| >= 3k contains k disjoint cycles. (C) 2016 Wiley Periodicals, Inc.