Strengthening theorems of Dirac and Erdős on disjoint cycles

2016/02/08 by Henry A. Kiersteád, Kierstead, Henry A., Alexandr Kostochka +3
Computer Science · Engineering · Mathematics · #05C10 #05C35 #05C70 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory #graph theory and CDMA systems

paper · pdf · doi:10.48550/arxiv.1602.02461

openalex publication_date 2016/02/08 · openalex created_date 2022/09/12 · openalex updated_date 2026/07/28

Abstract

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 Erdős proved that G contains k (vertex-)disjoint cycles whenever |H_k(G)| - |L_k(G)| ≥ k² + 2k - 4. The main result of this paper 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 Corrádi-Hajnal Theorem, which states that every graph G with H_k(G) = V(G) and |H_k(G)| ≥ 3k contains k disjoint cycles.

Citations

• On the maximal number of independent circuits in a graph

Related

• On the Corrádi-Hajnal Theorem and a question of Dirac
• A sharp Dirac-Erdős type bound for large graphs
• A refinement of theorems on vertex-disjoint chorded cycles
• The confirmation of a conjecture on disjoint cycles in a graph
• Cycles of given size in a dense graph