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 D2n/41. Then every D-regular graph G on n vertices has a decomposition into perfect matchings. Equivalently, (G)=D.
(ii) [ Hamilton decomposition conjecture] Suppose that Dn/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 regeven (n,)/2(n2)/8 edge-disjoint Hamilton cycles. Here regeven (n,) denotes the degree of the largest even-regular spanning subgraph one can guarantee in a graph on n vertices with minimum degree .
(i) was first explicitly stated by Chetwynd and Hilton. (ii) and the special case =n/2of (iii) answer questions of Nash-Williams from 1970. All of the above bounds are best possible.
|
|
|
1 | (14) |
|
|
|
1 | (4) |
|
|
|
5 | (1) |
|
1.3 Derivation of Theorems 1.1.1, 1.1.3, 1.1.4 from the Main Structural Results |
|
|
6 | (4) |
|
|
|
10 | (5) |
|
Chapter 2 The two cliques case |
|
|
15 | (54) |
|
2.1 Overview of the Proofs of Theorems 1.3.3 and 1.3.9 |
|
|
15 | (3) |
|
2.2 Partitions and Frameworks |
|
|
18 | (3) |
|
2.3 Exceptional Systems and (K, m, ε0)-Partitions |
|
|
21 | (3) |
|
2.4 Schemes and Exceptional Schemes |
|
|
24 | (3) |
|
2.5 Proof of Theorem 1.3.9 |
|
|
27 | (5) |
|
2.6 Eliminating the Edges inside A0 and B0 |
|
|
32 | (6) |
|
2.7 Constructing Localized Exceptional Systems |
|
|
38 | (4) |
|
2.8 Special Factors and Exceptional Factors |
|
|
42 | (8) |
|
2.9 The Robust Decomposition Lemma |
|
|
50 | (6) |
|
2.10 Proof of Theorem 1.3.3 |
|
|
56 | (13) |
|
Chapter 3 Exceptional systems for the two cliques case |
|
|
69 | (26) |
|
|
|
69 | (1) |
|
3.2 Non-critical Case with e(A', B') ≥ D |
|
|
70 | (10) |
|
3.3 Critical Case with e(A', B') ≥ D |
|
|
80 | (11) |
|
3.4 The Case when e(A', B') > D |
|
|
91 | (4) |
|
Chapter 4 The bipartite case |
|
|
95 | (48) |
|
4.1 Overview of the Proofs of Theorems 1.3.5 and 1.3.8 |
|
|
95 | (3) |
|
4.2 Eliminating Edges between the Exceptional Sets |
|
|
98 | (8) |
|
4.3 Finding Path Systems which Cover All the Edges within the Classes |
|
|
106 | (15) |
|
4.4 Special Factors and Balanced Exceptional Factors |
|
|
121 | (8) |
|
4.5 The Robust Decomposition Lemma |
|
|
129 | (5) |
|
4.6 Proof of Theorem 1.3.8 |
|
|
134 | (2) |
|
4.7 Proof of Theorem 1.3.5 |
|
|
136 | (7) |
|
Chapter 5 Approximate decompositions |
|
|
143 | (19) |
|
|
|
143 | (2) |
|
5.2 Systems and Balanced Extensions |
|
|
145 | (2) |
|
5.3 Finding Systems and Balanced Extensions for the Two Cliques Case |
|
|
147 | (4) |
|
5.4 Constructing Hamilton Cycles via Balanced Extensions |
|
|
151 | (6) |
|
|
|
157 | (5) |
| Acknowledgement |
|
162 | (1) |
| Bibliography |
|
163 | |
Bela Csaba, University of Szeged, Hungary.
Daniela Kuhn, University of Birmingham, United Kingdom.
Allan Lo, University of Birmingham, United Kingdom.
Deryk Osthus, University of Birmingham, United Kingdom.
Andrew Treglown, University of Birmingham, United Kingdom.
