Proof of the 1-factorization and Hamilton Decomposition Conjectures
Bela Csaba, Daniela Kuhn, Allan Lo, Deryk Osthus, Andrew Treglown, "Proof of the 1-factorization and Hamilton Decomposition Conjectures"
English | ISBN: 1470420252 | 2016 | 176 pages | PDF | 1 MB
English | ISBN: 1470420252 | 2016 | 176 pages | PDF | 1 MB
In this paper the authors 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, chi'(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 delta=>n/2. Then G contains at least regeven (n,delta)/2=>(n-2)/8 edge-disjoint Hamilton cycles. Here regeven (n,delta) denotes the degree of the largest even-regular spanning subgraph one can guarantee in a graph on n vertices with minimum degree delta. (i) was first explicitly stated by Chetwynd and Hilton. (ii) and the special case delta= n/2 of (iii) answer questions of Nash-Williams from 1970. All of the above bounds are best possible.