Proof of the 1-factorization and Hamilton Decomposition Conjectures
By Béla Csaba, D. Kühn, Allan Siu Lun Lo, Deryk Osthus, Andrew Treglown. 2014
117 citations recorded by the source corpus.
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⌈n/4⌉ − 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 ≥ ⌊n/2⌋. 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 (n − 2)/8 edge-disjoint Hamilton cycles. According to Dirac, (i) was first raised in the 1950’s. (ii) and (iii) answer questions of Nash-Williams from 1970. All of the above bounds are best possible.
Subfields: Discrete Mathematics and Combinatorics, Electrical and Electronic Engineering
View Paper: https://www.semanticscholar.org/paper/e5d9c7722d19b7d8a31244d2ef322d0d93b71797
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Discrete Mathematics and Combinatorics
In Electrical and Electronic Engineering
Citations in the corpus
- Hamilton cycles in graphs and hypergraphs: an extremal perspective (2014, background): “Recently, much attention has focused on the following areas, which we will discuss below: • Optimal packings of edge-disjoint Hamilton cycles, • Resilience and robustness.”