Proof of the 1-factorization and Hamilton decomposition conjectures III: approximate decompositions

Abstract

In a sequence of four papers, 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\ge 2\lceil n/4\rceil -1$. Then every $D$-regular graph $G$ on $n$ vertices has a decomposition into perfect matchings. Equivalently, ${\chi }^{\prime }(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) We prove an optimal result on the number of edge-disjoint Hamilton cycles in a graph of given minimum degree. According to Dirac, (i) was first raised in the 1950s. (ii) and (iii) answer questions of Nash-Williams from 1970. The above bounds are best possible. In the current paper, we show the following: suppose that $G$ is close to a complete balanced bipartite graph or to the union of two cliques of equal size. If we are given a suitable set of path systems which cover a set of `exceptional' vertices and edges of $G$, then we can extend these path systems into an approximate decomposition of $G$ into Hamilton cycles (or perfect matchings if appropriate).

We originally split the proof into four papers, of which this was the third paper. We have now combined this series into a single publication [arXiv:1401.4159v2], which will appear in the Memoirs of the AMS. 29 pages, 2 figures

References in corpus (2)

• Proof of the 1-factorization and Hamilton decomposition conjectures II: the bipartite case
• Proof of the 1-factorization and Hamilton decomposition conjectures IV: exceptional systems for the two cliques case

Cited by in corpus (5)

• Hamilton cycles in graphs and hypergraphs: an extremal perspective
• Proof of the 1-factorization and Hamilton decomposition conjectures II: the bipartite case
• Proof of the 1-factorization and Hamilton decomposition conjectures IV: exceptional systems for the two cliques case
• Packing, Counting and Covering Hamilton cycles in random directed graphs
• Vertex-transitive graphs that have no Hamilton decomposition