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

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 prove results on the decomposition of sparse graphs into path systems. These are used in the proof of (i) and (ii) in the case when $G$ is close to the union of two disjoint cliques.

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

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 III: approximate decompositions

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 III: approximate decompositions
• Packing, Counting and Covering Hamilton cycles in random directed graphs
• Vertex-transitive graphs that have no Hamilton decomposition