A density Corrádi-Hajnal theorem

Allen, Peter

; Hladký, Jan; and Piguet, Diana (2015) A density Corrádi-Hajnal theorem. Canadian Journal of Mathematics, 67 (4). pp. 721-758. ISSN 0008-414X

Copy

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 Corrádi-Hajnal Theorem.

Item Type	Article
Keywords	graph theory,Turan's Theorem,Mantel's Theorem,Corrádi-Hajnal Theorem,triangle
Departments	Mathematics
DOI	10.4153/CJM-2014-030-6
Date Deposited	20 Jul 2016 09:03
URI	https://researchonline.lse.ac.uk/id/eprint/67185