2014/01/16 by Csaba, Béla, Kühn, Daniela, Lo, Allan +2
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1401.4164
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) [Optimal packings of Hamilton cycles] Suppose that G is a graph on n vertices with minimum degree δ≥ n/2. Then G contains at least \rm reg\rm even(n,δ)/2 ≥ (n-2)/8 edge-disjoint Hamilton cycles. Here \rm reg\rm even(n,δ) denotes the degree of the largest even-regular spanning subgraph one can guarantee in a graph on n vertices with minimum degree δ. According to Dirac, (i) was first raised in the 1950s. (ii) and the special case δ= \lceil n/2 \rceil of (iii) answer questions of Nash-Williams from 1970. All of the above bounds are best possible. In the current paper, we prove the above results for the case when G is close to a complete balanced bipartite graph.