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

摘要

In 1963, Corradi and Hajnal settled a conjecture of Erdos by showing that every graph on at least 3r vertices with minimum degree at least 2r contains a collection of r disjoint cycles, and in 2008, Finkel proved that every graph with at least 4s vertices and minimum degree at least 3s 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 3r + 4s vertices and minimum degree at least 2r + 3s 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 3r + 4s vertices with minimum degree at least 2r + 3s- 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. (C) 2020 Elsevier B.V. All rights reserved.