Strengthening Theorems of Dirac and Erdős on Disjoint Cycles
Hal A. Kierstead, Alexandr V. Kostochka, Andrew McConvey · Journal of Graph Theory · 2016
Abstract Let be an integer, be the set of vertices of degree at least 2k in a graph G, and be the set of vertices of degree at most in G. In 1963, Dirac and Erdős proved that G contains k (vertex) disjoint cycles whenever . The main result of this article is that for , every graph G with containing at most t disjoint triangles and with contains k disjoint cycles. This yields that if and , then G contains k disjoint cycles. This generalizes the Corrádi–Hajnal Theorem, which states that every graph G with and contains k disjoint cycles.