eBook ISBN:  9781470435080 
Product Code:  MEMO/244/1154.E 
List Price:  $90.00 
MAA Member Price:  $81.00 
AMS Member Price:  $54.00 
eBook ISBN:  9781470435080 
Product Code:  MEMO/244/1154.E 
List Price:  $90.00 
MAA Member Price:  $81.00 
AMS Member Price:  $54.00 

Book DetailsMemoirs of the American Mathematical SocietyVolume: 244; 2016; 164 ppMSC: 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 (n2)/8\) edgedisjoint Hamilton cycles. Here \({\rm reg}_{\rm even}(n,\delta)\) denotes the degree of the largest evenregular 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 NashWilliams from 1970. All of the above bounds are best possible.

Table of Contents

Chapters

1. Introduction

2. The two cliques case

3. Exceptional systems for the two cliques case

4. The bipartite case

5. Approximate decompositions


Additional Material

RequestsReview Copy – for publishers of book reviewsPermission – for use of book, eBook, or Journal contentAccessibility – to request an alternate format of an AMS title
 Book Details
 Table of Contents
 Additional Material
 Requests
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 (n2)/8\) edgedisjoint Hamilton cycles. Here \({\rm reg}_{\rm even}(n,\delta)\) denotes the degree of the largest evenregular 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 NashWilliams 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