$K_r$-Factors in Graphs with Low Independence Number

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 $δ(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 $μ>0$ there is a positive constant $γ$ such that every graph $G$ on $n$ vertices with $δ(G)\ge \left(1-\frac{2}{r}+μ\right)n$ and $α(G) < γn$ has a $K_r$-factor. We also give examples showing the minimum degree condition is asymptotically best possible.

No reviews yet.

No comments yet.