Proof of the 1-Factorization and Hamilton Decomposition Conjectures

Csaba, Béla and Kühn, Daniela and Lo, Allan and Osthus, Deryk and Treglown, Andrew (2016) Proof of the 1-Factorization and Hamilton Decomposition Conjectures. American Mathematical Society, pp. 1-164. ISBN 978-1-4704-2025-3

Preview

Text memo775.pdf Download (1MB) | Preview

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 reg even (n, δ)/2 ≥ (n−2)/8 edge-disjoint Hamilton cycles. Here reg even (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.

Actions (login required)

Edit Item