My Holdings   Activate Remote Access

Proof of the $1$-factorization and Hamilton Decomposition Conjectures


About this Title

Béla Csaba, Daniela Kühn, Allan Lo, Deryk Osthus and Andrew Treglown

Publication: Memoirs of the American Mathematical Society
Publication Year: 2016; Volume 244, Number 1154
ISBNs: 978-1-4704-2025-3 (print); 978-1-4704-3508-0 (online)
DOI: http://dx.doi.org/10.1090/memo/1154
Published electronically: June 21, 2016
Keywords:1-factorization, Hamilton cycle, Hamilton decomposition

View full volume PDF

View other years and numbers:

Table of Contents


Chapters

  • Chapter 1. Introduction
  • Chapter 2. The two cliques case
  • Chapter 3. Exceptional systems for the two cliques case
  • Chapter 4. The bipartite case
  • Chapter 5. Approximate decompositions

Abstract


In this paper we prove the following results (via a unified approach) for all sufficiently large $n$: \item[(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$. \item[(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. \item[(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.

References [Enhancements On Off] (What's this?)