On a Ramsey-Turán Variant of the Hajnal-Szemerédi Theorem

Abstract

A seminal result of Hajnal and Szemeredi states that if a graph G with n vertices has minimum degree delta(G) >= (r - 1)n/r for some integer r >= 2, then G contains a K-r-factor, assuming r divides n. Extremal examples which show optimality of the bound on delta(G) are very structured and, in particular, contain large independent sets. In analogy to the Ramsey-Turan theory, Balogh, Molla, and Sharifzadeh initiated the study of how the absence of such large independent sets influences sufficient minimum degree. We show the following two related results: (a) For any r > l >= 2, if G is a graph satisfying delta(G) >= r-l/r-l+1 n+Omega(n) and alpha(l)(G) = o(n), that is, a largest K-l-free induced subgraph has at most o(n) vertices, then G contains a K-r-factor. This is optimal for l = r - 1 and extends a result of Balogh, Molla, and Sharifzadeh who considered the case r = 3. (b) If a graph G satisfies delta(G) = Omega(n) and alpha(r)*(G) = o(n), that is, every induced K-r-free r-partite subgraph of G has at least one vertex class of size o(n), then it contains a K-r-factor. A similar statement is proven for a general graph H.