In this paper we prove the following results (via a unified approach) for allsufficiently large $n$: (i) [$1$-factorization conjecture] Suppose that $n$ is even and $Dgeq2lceil n/4ceil -1$. Then every $D$-regular graph $G$ on $n$ vertices has adecomposition into perfect matchings. Equivalently, $chi'(G)=D$. (ii) [Hamilton decomposition conjecture] Suppose that $D ge lfloor n/2floor $. Then every $D$-regular graph $G$ on $n$ vertices has a decompositioninto 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 $deltage n/2$. Then $G$ contains at least${m reg}_{m even}(n,delta)/2 ge (n-2)/8$ edge-disjoint Hamilton cycles.Here $ext{reg}_{ext{even}}(n,delta)$ denotes the degree of the largesteven-regular spanning subgraph one can guarantee in a graph on $n$ verticeswith minimum degree $delta$. (i) was first explicitly stated by Chetwynd and Hilton. (ii) and the specialcase $delta= lceil n/2 ceil$ of (iii) answer questions of Nash-Williamsfrom 1970. All of the above bounds are best possible.
展开▼
机译：在本文中，我们针对所有足够大的$ n $证明了以下结果（通过统一方法）：（i）[$ 1 $-因式分解猜想]假设$ n $是偶数，而$ D geq2 lceil n / 4 rceil -1 $。然后，在$ n $顶点上的每个$ D $-正则图$ G $都会分解为完美的匹配。等效地，$ chi'（G）= D $。 （ii）[哈密尔顿分解猜想]假设$ D ge lfloor n / 2 rfloor $。然后，在$ n $个顶点上的每个$ D $-正则图$ G $都有分解为汉密尔顿循环，并且最多有一个完美的匹配。 （iii）[汉密尔顿循环的最佳堆积]假设$ G $是最小度为$ delta ge n / 2 $的$ n $个顶点的图。然后$ G $至少包含$ { rm reg} _ { rm even}（n， delta）/ 2 ge（n-2）/ 8 $个边缘不相交的汉密尔顿循环。这里$ text {reg} _ { text {even}}（n， delta）$表示一个人可以在图中最小度为$ delta $的$ n $个顶点上保证的最大偶数正则跨度子图的程度。 （i）由Chetwynd和Hilton首先明确声明。 （ii）和（iii）的特例$ delta = lceil n / 2 rceil $回答了1970年以来的Nash-Williams问题。以上所有界限都是最好的。
展开▼
