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].
MSC:
 05C42 Density (toughness, etc.)
Full Text: