On a Ramsey-Turán variant of the Hajnal-Szemerédi theorem

Abstract

A seminal result of Hajnal and Szemerédi states that if a graph $G$ with $n$ vertices has minimum degree $\delta (G)\ge (r-1)n/r$ for some integer $r\ge 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-Turán 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: $\bullet$ For any $r>\ell \ge 2$, if $G$ is a graph satisfying $\delta (G)\ge (r-\ell )n/(r-\ell +1)+\Omega (n)$ and ${\alpha }_{\ell }(G)=o(n)$, that is, a largest $K_{\ell }$-free induced subgraph has at most $o(n)$ vertices, then $G$ contains a $K_r$-factor. This is optimal for $\ell =r-1$ and extends a result of Balogh, Molla, and Sharifzadeh who considered the case $r=3$. $\bullet$ If a graph $G$ satisfies $\delta (G)=\Omega (n)$ and ${\alpha }_r^{\ast }(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$.