An error was encountered while trying to add the item to the cart. Please try again.
Copy To Clipboard
Successfully Copied!
Proof of the 1-Factorization and Hamilton Decomposition Conjectures

Béla Csaba University of Szeged, Hungary
Daniela Kühn 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
Available Formats:
Electronic ISBN: 978-1-4704-3508-0
Product Code: MEMO/244/1154.E
List Price: $90.00 MAA Member Price:$81.00
AMS Member Price: $54.00 Click above image for expanded view Proof of the 1-Factorization and Hamilton Decomposition Conjectures Béla Csaba University of Szeged, Hungary Daniela Kühn 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 Available Formats:  Electronic ISBN: 978-1-4704-3508-0 Product Code: MEMO/244/1154.E  List Price:$90.00 MAA Member Price: $81.00 AMS Member Price:$54.00
• Book Details

Memoirs of the American Mathematical Society
Volume: 2442016; 164 pp
MSC: Primary 05;

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 $D\geq 2\lceil n/4\rceil -1$. Then every $D$-regular graph $G$ on $n$ vertices has a decomposition into perfect matchings. Equivalently, $\chi'(G)=D$.

(ii) [Hamilton decomposition conjecture] Suppose that $D \ge \lfloor n/2 \rfloor$. 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 $\delta\ge n/2$. Then $G$ contains at least ${\rm reg}_{\rm even}(n,\delta)/2 \ge (n-2)/8$ edge-disjoint Hamilton cycles. Here ${\rm reg}_{\rm even}(n,\delta)$ denotes the degree of the largest even-regular spanning subgraph one can guarantee in a graph on $n$ vertices with minimum degree $\delta$.

(i) was first explicitly stated by Chetwynd and Hilton. (ii) and the special case $\delta= \lceil n/2 \rceil$ of (iii) answer questions of Nash-Williams from 1970. All of the above bounds are best possible.

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

• Requests

Review Copy – for reviewers who would like to review an AMS book
Permission – for use of book, eBook, or Journal content
Accessibility – to request an alternate format of an AMS title
Volume: 2442016; 164 pp
MSC: Primary 05;

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 $D\geq 2\lceil n/4\rceil -1$. Then every $D$-regular graph $G$ on $n$ vertices has a decomposition into perfect matchings. Equivalently, $\chi'(G)=D$.

(ii) [Hamilton decomposition conjecture] Suppose that $D \ge \lfloor n/2 \rfloor$. 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 $\delta\ge n/2$. Then $G$ contains at least ${\rm reg}_{\rm even}(n,\delta)/2 \ge (n-2)/8$ edge-disjoint Hamilton cycles. Here ${\rm reg}_{\rm even}(n,\delta)$ denotes the degree of the largest even-regular spanning subgraph one can guarantee in a graph on $n$ vertices with minimum degree $\delta$.

(i) was first explicitly stated by Chetwynd and Hilton. (ii) and the special case $\delta= \lceil n/2 \rceil$ of (iii) answer questions of Nash-Williams from 1970. All of the above bounds are best possible.

• Chapters
• 1. Introduction
• 2. The two cliques case
• 3. Exceptional systems for the two cliques case
• 4. The bipartite case
• 5. Approximate decompositions
Review Copy – for reviewers who would like to review an AMS book
Permission – for use of book, eBook, or Journal content
Accessibility – to request an alternate format of an AMS title
Please select which format for which you are requesting permissions.