Proof of the 1-Factorization and Hamilton Decomposition Conjectures PDF
by Bela Csaba
Description
In this paper the authors prove the following results (via a unified approach) for all sufficiently large $n$: (i) [$1$-factorization conjecture] Suppose that $n$ is even and $D\geq 2\lceil n/4\rceil -1$.
Then every $D$-regular graph $G$ on $n$ vertices has a decomposition into perfect matchings.
Equivalently, $\chi'(G)=D$. (ii) [Hamilton decomposition conjecture] Suppose that $D \ge \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 $\delta\ge n/2$.
Then $G$ contains at least ${\rm reg}_{\rm even}(n,\delta)/2 \ge (n-2)/8$ edge-disjoint Hamilton cycles.
Here ${\rm reg}_{\rm even}(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= \lceil n/2 \rceil$ of (iii) answer questions of Nash-Williams from 1970.
All of the above bounds are best possible.
Information
-
Download - Immediately Available
- Format:PDF
- Publisher:American Mathematical Society
- Publication Date:10/05/2016
- Category:
- ISBN:9781470435080
Other Formats
- Paperback / softback from £79.00
Information
-
Download - Immediately Available
- Format:PDF
- Publisher:American Mathematical Society
- Publication Date:10/05/2016
- Category:
- ISBN:9781470435080