| Abstract: | The Hajnal-Szemerédi Theorem Hajnal & Szemerédi, Colloq Math Soc J Bolyai, 1970] states that a graph with hk vertices and minimum degree at least (h − 1)k contains k vertex disjoint copies of Kh. Its proof is not algorithmic. Here, we present an algorithm that, for a fixed h, finds in such a graph k − C(h) vertex disjoint copies of Kh in polynomial time in k, C(h) being a constant depending on h only. The proof suggests a variant of the theorem for h-partite graphs, which is conjectured here and proven in a slightly weaker form in some special cases. © 1999 John Wiley & Sons, Inc. J Graph Theory 31: 275–282, 1999 |
