Item Successfully Added to Cart
An error was encountered while trying to add the item to the cart. Please try again.
OK
Please make all selections above before adding to cart
OK
Share this page via the icons above, or by copying the link below:
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
Proof of the 1-Factorization and Hamilton Decomposition Conjectures
eBook 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
Proof of the 1-Factorization and Hamilton Decomposition Conjectures
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
eBook 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.

  • 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
     
     
  • Requests
     
     
    Review Copy – for publishers of book reviews
    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 publishers of book reviews
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.