On multipartite Hajnal-Szemerédi theorems

Abstract

Let $G$ be a $k$-partite graph with $n$ vertices in parts such that each vertex is adjacent to at least ${\delta }^{\ast }(G)$ vertices in each of the other parts. Magyar and Martin \cite{MaMa} proved that for $k=3$, if ${\delta }^{\ast }(G)\ge 2/3n$ and $n$ is sufficiently large, then $G$ contains a $K_3$-factor (a spanning subgraph consisting of $n$ vertex-disjoint copies of $K_3$) except that $G$ is one particular graph. Martin and Szemerédi \cite{MaSz} proved that $G$ contains a $K_4$-factor when ${\delta }^{\ast }(G)\ge 3/4n$ and $n$ is sufficiently large. Both results were proved by the Regularity Lemma. In this paper we give a proof of these two results by the absorbing method. Our absorbing lemma actually works for all $k\ge 3$.

15 pages, no figure

References in corpus (2)

• A Multipartite Hajnal-Szemerédi Theorem
• A multipartite version of the Hajnal-Szemerédi theorem for graphs and hypergraphs

Cited by in corpus (1)

• A multipartite version of the Hajnal-Szemerédi theorem for graphs and hypergraphs