A multipartite version of the Hajnal-Szemerédi theorem for graphs and hypergraphs
2013 (English)In: Combinatorics, probability & computing, ISSN 0963-5483, E-ISSN 1469-2163, Vol. 22, no 1, 97-111 p.Article in journal (Refereed) Published
A perfect Kt-matching in a graph G is a spanning subgraph consisting of vertex-disjoint copies of Kt A classic theorem of Hajnal and Szemerédi states that if G is a graph of order n with minimum degree δ(G) ≥(t - 1)n/t and t|n, then G contains a perfect Kt-matching. Let G be a t-partite graph with vertex classes V1, . . . , Vt each of size n. We show that, for any γ > 0, if every vertex x ∈ Vi is joined to at least ((t - 1)/t + γ )n vertices of Vj for each j ≠ i, then G contains a perfect Kt-matching, provided n is large enough. Thus, we verify a conjecture of Fischer  asymptotically. Furthermore, we consider a generalization to hypergraphs in terms of the codegree.
Place, publisher, year, edition, pages
New York, NJ, USA: Cambridge University Press, 2013. Vol. 22, no 1, 97-111 p.
Perfect matchings, Uniform hypergraphs
IdentifiersURN: urn:nbn:se:umu:diva-62999DOI: 10.1017/S096354831200048XOAI: oai:DiVA.org:umu-62999DiVA: diva2:580845