zbMATH — the first resource for mathematics

A density Corrádi-Hajnal theorem. (English) Zbl 1274.05276
Nešetřil, Jarik (ed.) et al., Extended abstracts of the sixth European conference on combinatorics, graph theory and applications, EuroComb 2011, Budapest, Hungary, August 29 – September 2, 2011. Amsterdam: Elsevier. Electronic Notes in Discrete Mathematics 38, 31-36 (2011).
Summary: For \(n\) sufficiently large, we determine the density threshold for an \(n\)-vertex graph to contain \(k\) vertex-disjoint triangles, where \(0\leq k\leq \frac{n}{3}\). This extends results by Erdős and by Moon, and can be viewed as a density version of the Corrádi-Hajnal theorem.
For the entire collection see [Zbl 1242.05003].
05C42 Density (toughness, etc.)
Full Text: Link