Variants of the Hajnal-Szemer�di Theorem

✍ Scribed by Fischer, Eldar

• Publisher: John Wiley and Sons
• Year: 1999
• Tongue: English
• Weight: 245 KB
• Volume: 31
• Category: Article
• ISSN: 0364-9024
• DOI: 10.1002/(sici)1097-0118(199908)31:4<275::aid-jgt2>3.0.co;2-f

✦ Synopsis

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 K h . 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 K h 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.