Approximate Multipartite Version of the Hajnal--Szemerédi Theorem

Abstract

Let $q$ be a positve integer, and $G$ be a $q$-partite simple graph on $qn$ vertices, with $n$ vertices in each vertex class. Let $\delta =\frac{k_q}{k_q+1}$, where $k_q=q+O(\log q)$. If each vertex of $G$ is adjacent to at least $\delta n$ vertices in each of the other vertex classes, $q$ is bounded and $n$ is large enough, then $G$ has a $K_q$-factor.

14 pages