A density Corrádi-Hajnal Theorem

Peter Allen, Julia Böttcher, Jan Hladký, Diana Piguet

Published 2014-03-15, updated 2014-07-30Version 2

We find, for all sufficiently large $n$ and each $k$, the maximum number of edges in an $n$-vertex graph which does not contain $k+1$ vertex-disjoint triangles. This extends a result of Moon [Canad. J. Math. 20 (1968), 96-102] which is in turn an extension of Mantel's Theorem. Our result can also be viewed as a density version of the Corradi-Hajnal Theorem.