Proof of the 1-factorization and Hamilton decomposition conjectures

MaRDI QIDQ5420009zbMATH OpenFDO

Authors Béla Csaba, Daniela Kühn, Allan Lo, Deryk Osthus, Andrew Treglown

Publication date 11 June 2014

Full work available at URL https://arxiv.org/abs/1401.4159

Mathematics Subject Classification ID

Eulerian and Hamiltonian graphs (05C45) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: In this paper we prove the following results (via a unified approach) for all sufficiently large $n$: (i) [$1$-factorization conjecture] Suppose that $n$ is even and $Dgeq2lceiln/4ceil-1$. Then every $D$-regular graph $G$ on $n$ vertices has a decomposition into perfect matchings. Equivalently, $ch{i}^{\prime }(G)=D$. (ii) [Hamilton decomposition conjecture] Suppose that $Dgelfloorn/2floor$. 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 $deltagen/2$. Then $G$ contains at least ${mreg}_{meven}(n,delta)/2ge(n-2)/8$ edge-disjoint Hamilton cycles. Here $ext{reg}_{exteven}(n,delta)$ denotes the degree of the largest even-regular spanning subgraph one can guarantee in a graph on $n$ vertices with minimum degree $delta$. (i) was first explicitly stated by Chetwynd and Hilton. (ii) and the special case $delta=lceiln/2ceil$ of (iii) answer questions of Nash-Williams from 1970. All of the above bounds are best possible.

Recommendations

• Proof of the 1-factorization and Hamilton Decomposition Conjectures
• Random matchings which induce Hamilton cycles and Hamiltonian decompositions of random regular graphs
• Edge-disjoint Hamilton cycles in graphs
• Solution to a problem of Bollobás and Häggkvist on Hamilton cycles in regular graphs
• The number of Hamiltonian decompositions of regular graphs

Cited in

(12)

• Hamiltonian decompositions of random bipartite regular graphs.
• Hamilton cycles in sparse robustly expanding digraphs
• The number of Hamiltonian decompositions of regular graphs
• Random matchings which induce Hamilton cycles and Hamiltonian decompositions of random regular graphs
• Hamilton decompositions of regular expanders: applications
• Solution to a problem of Bollobás and Häggkvist on Hamilton cycles in regular graphs
• Hamilton decompositions of some line graphs
• scientific article; zbMATH DE number 825148 (Why is no real title available?)
• Proof of the 1-factorization and Hamilton Decomposition Conjectures
• A note on Hamilton decompositions of even-regular multigraphs
• Edge-disjoint Hamilton cycles in graphs
• On the number of disjoint perfect matchings of regular graphs with given edge connectivity

This page was built for publication: Proof of the 1-factorization and Hamilton decomposition conjectures

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5420009)