Change search
ReferencesLink to record
Permanent link

Direct link
A multipartite version of the Hajnal-Szemerédi theorem for graphs and hypergraphs
Univ Birmingham, Sch Math, Birmingham B15 2TT, W Midlands, England.
Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
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
Abstract [en]

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 [6] 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.
Keyword [en]
Perfect matchings, Uniform hypergraphs
National Category
URN: urn:nbn:se:umu:diva-62999DOI: 10.1017/S096354831200048XOAI: diva2:580845
Available from: 2012-12-27 Created: 2012-12-27 Last updated: 2013-01-07Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full text

Search in DiVA

By author/editor
Markström, Klas
By organisation
Department of Mathematics and Mathematical Statistics
In the same journal
Combinatorics, probability & computing

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 37 hits
ReferencesLink to record
Permanent link

Direct link