A degree sequence Hajnal-Szemeredi theorem

作者：Treglown Andrew

来源：Journal of Combinatorial Theory - Series B, 2016, 118: 13-43.

DOI：10.1016/j.jctb.2016.01.007

• Perfect packing
• Absorbing method
• Regularity method

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-Szemeredi theorem [12] characterises the minimum degree that ensures a graph G contains a perfect K-r-packing. Balogh, Kostochka and Treglown [4] proposed a degree sequence version of the Hajnal-Szemeredi theorem which, if true, gives a strengthening of the Hajnal-Szemeredi theorem. In this paper we prove this conjecture asymptotically. Another fundamental result in the area is the Alon-Yuster theorem [3] 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 [4] 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.

• 出版日期2016-5