Projects per year
Abstract
In this paper 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 regeven(n, Δ)/2 ≥ (n-2)/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/2] of (iii) answer questions of Nash-Williams from 1970. All of the above bounds are best possible.
Original language | English |
---|---|
Pages (from-to) | 1-164 |
Number of pages | 164 |
Journal | Memoirs of the American Mathematical Society |
Volume | 244 |
Issue number | 1154 |
Early online date | 21 Jun 2016 |
DOIs | |
Publication status | E-pub ahead of print - 21 Jun 2016 |
Fingerprint
Dive into the research topics of 'Proof of the 1-factorization and Hamilton decomposition conjectures'. Together they form a unique fingerprint.Projects
- 2 Finished
-
Edge-Colourings and Hamilton Decompostitions of Graphs
Engineering & Physical Science Research Council
1/06/12 → 30/09/14
Project: Research Councils
-
FP7- ERC - QRGraph: Quasirandomness in Graphs and Hypergraphs
European Commission, European Commission - Management Costs
1/12/10 → 30/11/15
Project: Research
Prizes
-
Fulkerson prize 2021
Csaba, Bela (Recipient), Kuhn, Daniela (Recipient), Lo, Allan (Recipient), Osthus, Deryk (Recipient) & Treglown, Andrew (Recipient), 27 Jul 2021
Prize: Prize (including medals and awards)