On multipartite Hajnal-Szemerédi theorems

Details On multipartite Hajnal-Szemerédi theorems On multipartite Hajnal-Szemerédi theorems

2012-03-12

arxiv.org/abs/1203.2667v1

Mathematics

Combinatorics

15 pages, no figure

Scientific paper

Let $G$ be a $k$-partite graph with $n$ vertices in parts such that each vertex is adjacent to at least $\delta^*(G)$ vertices in each of the other parts. Magyar and Martin \cite{MaMa} proved that for $k=3$, if $\delta^*(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\'edi \cite{MaSz} proved that $G$ contains a $K_4$-factor when $\delta^*(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$.

Affiliated with

Also associated with

No associations

Rating

On multipartite Hajnal-Szemerédi theorems does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On multipartite Hajnal-Szemerédi theorems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On multipartite Hajnal-Szemerédi theorems will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-143227