Triangle factors of graphs without large independent sets and of weighted graphs

The classical Corrádi‐Hajnal theorem claims that every n ‐vertex graph G with δ ( G ) ≥ 2 n / 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 ) = o ( 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 K r ‐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 ( K n ) → [ 0 , 1 ] . We call a triangle t‐heavy if the sum of the weights on its edges is more than 3 t . 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 + 2 t 3 + o ( 1 ) ) n , then there are n / 3 vertex disjoint heavy triangles in G . © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 49, 669–693, 2016