Proof of the 1-Factorization and Hamilton Decomposition Conjectures (eBook)

Bela Csaba (Autor)

eBook Download: PDF

2016
164 Seiten
American Mathematical Society (Verlag)
978-1-4704-3508-0 (ISBN)

Infos

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.

Produkt-Details

• Erscheint lt. Verlag: 10.5.2016
• Themenwelt: Mathematik / Informatik ► Mathematik ► Graphentheorie
• ISBN-10: 1-4704-3508-X / 147043508X
• ISBN-13: 978-1-4704-3508-0 / 9781470435080