Proof of the 1-factorization and Hamilton Decomposition Conjectures
Proof of the 1-factorization and Hamilton Decomposition Conjectures
复制标题
DOI：
10.1090/memo/1154
复制
发表时间：
2014-01
影响因子：
6.4
通讯作者：
Béla Csaba;D. Kuhn;A. Lo;Deryk Osthus;Andrew Treglown
中科院分区：
文献类型：
--
作者：
Béla Csaba;D. Kuhn;A. Lo;Deryk Osthus;Andrew Treglown
(I)[1-因子分解猜想]设n是偶数且D≥2⌈n/4⌉−1，则n个顶点上的每个D-正则图G都有一个完全匹配分解。等价地，χ‘(G)=D.(Ii)[哈密尔顿分解猜想]假设D≥⌊n/2⌋.则n个顶点上的每个D-正则图G都有一个哈密尔顿圈分解，且至多有一个完美匹配。(Iii)[哈密尔顿圈的最优包装]设G是一个最小度为δ≥n/2的n点图，则G至少包含(n−2)/8个边不相交的哈密尔顿圈。根据狄拉克的说法，(一)最早是在20世纪50年代提出的S。(2)和(3)回答纳什-威廉姆斯从1970年开始的问题。以上所有界限都是最好的可能。
We prove the following results (via a unified approach) for all sufficiently large n: (i) [1 -factorization conjecture] Suppose that n is even and D ≥ 2⌈n/4⌉ − 1. Then every D-regular graph G on n vertices has a decomposition into perfect matchings. Equivalently, χ′(G) = D. (ii) [Hamilton decomposition conjecture] Suppose that D ≥ ⌊n/2⌋. Then every D-regular graph G on n vertices has a decomposition into Hamilton cycles and at most one perfect matching. (iii) [Optimal packings of Hamilton cycles] Suppose that G is a graph on n vertices with minimum degree δ ≥ n/2. Then G contains at least (n − 2)/8 edge-disjoint Hamilton cycles. According to Dirac, (i) was first raised in the 1950’s. (ii) and (iii) answer questions of Nash-Williams from 1970. All of the above bounds are best possible.