2014/01/16 by Daniela Kühn, Allan Lo, Kühn, Daniela +3 · 6 citations
Engineering · Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #Finite Group Theory Research #Limits and Structures in Graph Theory #graph theory and CDMA systems #math.CO
paper · pdf · doi:10.48550/arxiv.1401.4183
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
openalex publication_date 2014/01/16 · arxiv created 2014/10/23 · arxiv updated 2014/10/24 · openalex created_date 2025/10/24 · openalex updated_date 2026/07/28
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≥ 2\lceil n/4\rceil -1. Then every D-regular graph G on n vertices has a decomposition into perfect matchings. Equivalently, χ'(G)=D. (ii) [Hamilton decomposition conjecture] Suppose that D ≥ \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.