$K_r$-Factors in Graphs with Low Independence Number

Abstract

A classical result by Hajnal and Szemerédi from 1970 determines the minimal degree conditions necessary to guarantee for a graph to contain a $K_r$-factor. Namely, any graph on $n$ vertices, with minimum degree $\delta (G)\ge \left(1-\frac{1}{r}\right)n$ and $r$ dividing $n$ has a $K_r$-factor. This result is tight but the extremal examples are unique in that they all have a large independent set which is the bottleneck. Nenadov and Pehova showed that by requiring a sub-linear independence number the minimum degree condition in the Hajnal-Szemerédi theorem can be improved. We show that, with the same minimum degree and sub-linear independence number, we can find a clique-factor with double the clique size. More formally, we show for every $r\in \mathbb{N}$ and constant $\mu >0$ there is a positive constant $\gamma$ such that every graph $G$ on $n$ vertices with $\delta (G)\ge \left(1-\frac{2}{r}+\mu \right)n$ and $\alpha (G)<\gamma n$ has a $K_r$-factor. We also give examples showing the minimum degree condition is asymptotically best possible.