A degree sequence Hajnal-Szemerédi theorem
A degree sequence Hajnal-Szemerédi theorem
复制标题
A 度序列 Hajnal-Szemeredi 定理
DOI：
10.1016/j.jctb.2016.01.007
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
Andrew Treglown
中科院分区：
文献类型：
--
作者：
Andrew Treglown
我们称图G是完美H-填充的，如果存在一组顶点不相交的H的副本，这些副本覆盖了图G中的所有顶点。开创性的Hajnal-Szemerédi定理[12]刻画了确保图G包含完美Kr-填充的最小度。Balogh、Kostochka和Treglown [4]提出了Hajnal-Szemerédi定理的一个度序列版本，如果它为真，则加强了Hajnal-Szemerédi定理。在本文中，我们渐进地证明了这个猜想。该领域的另一个基本结果是Alon-Yuster定理[3]，它给出了一个最小度条件，该条件确保图包含任意图H的完美H-填充。我们通过回答Balogh，Kostochka和Treglown [4]关于图的度序列的另一个猜想，给出了这个结果的一个广泛的推广，这个猜想迫使一个完美的H-包装。我们还证明了一个关于有向图中完全传递竞赛填充的度序列结果。证明将规律性和吸收方法融为一体。
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 K r-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.
影响因子：
1.1
作者：
D. Kühn;Deryk Osthus
通讯作者：
D. Kühn;Deryk Osthus