A degree sequence Hajnal-Szemerédi theorem

详细信息    查看全文

• 作者：Andrew Treglown ^{a.c.treglown@bham.ac.uk" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Perfect packing ; Absorbing method ; Regularity method
• 刊名：Journal of Combinatorial Theory, Series B
• 出版年：2016
• 出版时间：May 2016
• 年：2016
• 卷：118
• 期：Complete
• 页码：13-43
• 全文大小：585 K

文摘

We say that a graph G has a perfect H-packing if there exists a set of vertex-disjoint copies of H which cover all the vertices in G. The seminal Hajnal–Szemerédi theorem an id="bbr0120">[12]a>an> characterises the minimum degree that ensures a graph G   contains a perfect an id="mmlsi1" class="mathmlsrc">an class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0095895616000095&_mathId=si1.gif&_user=111111111&_pii=S0095895616000095&_rdoc=1&_issn=00958956&md5=7f7955ff71691728b7ad4b7edeedb83e" title="Click to view the MathML source">K_ran>an class="mathContainer hidden">an class="mathCode">ath altimg="si1.gif" overflow="scroll">Krath>an>an>an>-packing. Balogh, Kostochka and Treglown an id="bbr0040">[4]a>an> proposed a degree sequence version of the Hajnal–Szemerédi theorem which, if true, gives a strengthening of the Hajnal–Szemerédi theorem. In this paper we prove this conjecture asymptotically. Another fundamental result in the area is the Alon–Yuster theorem an id="bbr0030">[3]a>an> which gives a minimum degree condition that ensures a graph contains a perfect H-packing for an arbitrary graph H. We give a wide-reaching generalisation of this result by answering another conjecture of Balogh, Kostochka and Treglown an id="bbr0040">[4]a>an> on the degree sequence of a graph that forces a perfect H-packing. We also prove a degree sequence result concerning perfect transitive tournament packings in directed graphs. The proofs blend together the regularity and absorbing methods.