A Density Version of the Corradi-Hajnal Theorem

2014/10/01 by Dieter Rautenbach, Bruce Reed, Rautenbach, Dieter +1
Computer Science · Engineering · Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory #graph theory and CDMA systems

paper · pdf · doi:10.48550/arxiv.1410.0197

openalex publication_date 2014/10/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

For every positive integer k, we show that every graph of order n at least 3k with more than max\2k-1\choose 2+(2k-1)(n-(2k-1)),3k-1\choose 2+(n-(3k-1))\ edges has k vertex disjoint cycles, which is a best possible density version of a theorem of Corrádi and Hajnal.

Related

• Density Hajnal--Szemerédi theorem for cliques of size four
• A step towards a general density Corrádi--Hajnal Theorem
• Cycles of given size in a dense graph
• On the Corrádi-Hajnal Theorem and a question of Dirac
• Toward a density Corrádi--Hajnal theorem for degenerate hypergraphs