A density Corrádi-Hajnal Theorem

Abstract

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.

41 pages (including 11 pages of appendix), 4 figures, 2 tables

References in corpus (2)

• The extremal function for partial bipartite tilings
• Turánnical hypergraphs

Cited by in corpus (5)

• Komlós's tiling theorem via graphon covers
• Tilings in graphons
• A median-type condition for graph tiling
• On the multicolor Turán conjecture for color-critical graphs
• A Ramsey-Turán theory for tilings in graphs