Article ID Journal Published Year Pages File Type
6424550 Journal of Combinatorial Theory, Series B 2015 50 Pages PDF
Abstract

The celebrated Hajnal-Szemerédi theorem gives the precise minimum degree threshold that forces a graph to contain a perfect Kk-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.

Keywords
Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, ,