کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4656704 | 1632975 | 2016 | 31 صفحه PDF | دانلود رایگان |
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 [12] characterises the minimum degree that ensures a graph G contains a perfect KrKr-packing. Balogh, Kostochka and Treglown [4] 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 [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.
Journal: Journal of Combinatorial Theory, Series B - Volume 118, May 2016, Pages 13–43