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)
- Triangle-factors in pseudorandom graphs
- On factors of independent transversals in -partite graphs
- A multipartite version of the Hajnal-Szemerédi theorem for graphs and hypergraphs
- Powers of Hamiltonian cycles in multipartite graphs
- An asymptotic multipartite Kühn-Osthus theorem
- On Perfect Matchings in -complexes
- Tiling tripartite graphs with 3-colorable graphs: The extreme case
- Rainbow spanning structures in graph and hypergraph systems
- On multipartite Hajnal-Szemerédi theorems
- -Factors in Graphs with Low Independence Number
- Embedding clique-factors in graphs with low -independence number