paper

A Multipartite Hajnal-Szemerédi Theorem

arXiv:1201.1882 · doi:10.1016/j.jctb.2015.04.003

Abstract

The celebrated Hajnal-Szemerédi theorem gives the precise minimum degree threshold that forces a graph to contain a perfect K_k-packing. Fischer's conjecture states that the analogous result holds for all multipartite graphs except for those formed by a single construction. Recently, we deduced an approximate version of this conjecture from new results on perfect matchings in hypergraphs. In this paper, we apply a stability analysis to the extremal cases of this argument, thus showing that the exact conjecture holds for any sufficiently large graph.

arXiv commentFinal version, accepted to appear in JCTB. 43 pages, 2 figures

References in corpus (2)

Cited by in corpus (11)