2014/01/16 by Béla Csaba, Csaba, Béla, Daniela Kühn +7 · 4 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.4178
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
openalex publication_date 2014/01/16 · arxiv created 2014/10/23 · arxiv updated 2014/10/24 · openalex created_date 2016/06/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 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).