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

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

2011-08-21

arxiv.org/abs/1108.4184v1

Mathematics

Combinatorics

14 pages

Scientific paper

A perfect $K_t$-matching in a graph $G$ is a spanning subgraph consisting of vertex disjoint copies of $K_t$. A classic theorem of Hajnal and Szemer\'edi states that if $G$ is a graph of order $n$ with minimum degree $\delta(G) \ge (t-1)n/t$ and $t| n$, then $G$ contains a perfect $K_t$-matching. Let $G$ be a $t$-partite graph with vertex classes $V_1$,..., $V_t$ each of size $n$. We show that if every vertex $x \in V_i$ is joined to at least $((t-1)/t + \gamma)n $ vertices of $V_j$ for $i \ne j$, then $G$ contains a perfect $K_t$-matching, thus verifying a conjecture of Fisher asymptotically. Furthermore, we consider a generalisation to hypergraphs in terms of the codegree.

Affiliated with

Also associated with

No associations

Rating

A multipartite version of the Hajnal-Szemerédi theorem for graphs and hypergraphs 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 A multipartite version of the Hajnal-Szemerédi theorem for graphs and hypergraphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A multipartite version of the Hajnal-Szemerédi theorem for graphs and hypergraphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-537836