Disjoint cycles and chorded cycles in a graph with given minimum degree

Abstract In 1963, Corradi and Hajnal settled a conjecture of Erdős by showing that every graph on at least 3 r vertices with minimum degree at least 2 r contains a collection of r disjoint cycles, and in 2008, Finkel proved that every graph with at least 4 s vertices and minimum degree at least 3 s contains a collection of s disjoint chorded cycles. The same year, a generalization of this theorem was conjectured by Bialostocki, Finkel, and Gyarfas: every graph with at least 3 r + 4 s vertices and minimum degree at least 2 r + 3 s contains a collection of r + s disjoint cycles, s of them chorded. This conjecture was settled and further strengthened by Chiba et al. (2010). In this paper, we characterize all graphs on at least 3 r + 4 s vertices with minimum degree at least 2 r + 3 s − 1 that do not contain a collection of r + s disjoint cycles, s of them chorded. In addition, we provide a conjecture regarding the minimum degree threshold for the existence of r + s disjoint cycles, s of them chorded, and we prove an approximate version of this conjecture.