A Multipartite Hajnal-Szemerédi Theorem

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.

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

References in corpus (2)

• Tripartite Version of the Corrádi-Hajnal Theorem
• A multipartite version of the Hajnal-Szemerédi theorem for graphs and hypergraphs

Cited by in corpus (11)

• Triangle-factors in pseudorandom graphs
• On factors of independent transversals in $k$-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 $k$-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
• $K_r$-Factors in Graphs with Low Independence Number
• Embedding clique-factors in graphs with low $\ell$-independence number