Projects per year
Abstract
In this paper we prove the following results (via a unified approach) for all sufficiently large n: (i) [1factorization conjecture] Suppose that n is even and D ≥ 2[n/4]  1. Then every Dregular 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 Dregular 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 reg_{even}(n, Δ)/2 ≥ (n2)/8 edgedisjoint Hamilton cycles. Here reg_{even}(n, Δ) denotes the degree of the largest evenregular 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 NashWilliams from 1970. All of the above bounds are best possible.
Original language  English 

Pages (fromto)  1164 
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  Epub ahead of print  21 Jun 2016 
Fingerprint
Dive into the research topics of 'Proof of the 1factorization and Hamilton decomposition conjectures'. Together they form a unique fingerprint.Projects
 2 Finished

EdgeColourings 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)