The classical Corrádi-Hajnal theorem claims that every n-vertex graph G with δ(G)≥2n/3 contains a triangle factor, when 3|n. In this paper we present two related results that both use the absorbing technique of Rödl, Ruciński and Szemerédi. Our main result determines the minimum degree condition necessary to guarantee a triangle factor in graphs with sublinear independence number. In particular, we show that if G is an n-vertex graph with α(G) = on(n) and δ(G) ≥(1/2 + o(1))n, then G has a triangle factor and this is asymptotically best possible. Furthermore, it is shown for every r that if every linear size vertex set of a graph G spans quadratically many edges, and δ(G) ≥(1/2 + o(1))n, then G has a Kr-factor for n sufficiently large. We also propose many related open problems whose solutions could show a relationship with Ramsey-Turán theory. Additionally, we also consider a fractional variant of the Corrádi-Hajnal Theorem, settling a conjecture of Balogh-Kemkes-Lee-Young. Let t є (0,1) and w : E(Kn) → [0,1]. We call a triangle t-heavy if the sum of the weights on its edges is more than 3t. We prove that if 3|n and w is such that for every vertex v the sum of w(e) over edges e incident to v is at least (1+2t/3 + o(1))n, then there are n/3 vertex disjoint heavy triangles in G.
- extremal problems
- matching, partitioning, covering and packing
- probabilistic methods
ASJC Scopus subject areas
- Computer Graphics and Computer-Aided Design
- Applied Mathematics