pith. sign in

arxiv: 1108.4184 · v2 · pith:QU37UFRKnew · submitted 2011-08-21 · 🧮 math.CO

A multipartite version of the Hajnal-Szemer\'edi theorem for graphs and hypergraphs

classification 🧮 math.CO
keywords graphmatchingperfectvertexcontainshypergraphsthentheorem
0
0 comments X
read the original abstract

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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.