Nash-Williams's Hamilton cycle packing conjecture

About 17 years old · traced to

Let GG be a graph on nn vertices, let δ(G)\delta(G) denote its minimum degree, and let reg⁡even⁡(G)\operatorname{reg}_{\operatorname{even}}(G) denote the degree of a largest even-regular spanning subgraph of GG.

Nash-Williams's conjecture. Suppose that GG is a graph on nn vertices with minimum degree

δ(G)≥n/2.\delta(G)\ge n/2.

Then GG contains reg⁡even⁡(G)/2\operatorname{reg}_{\operatorname{even}}(G)/2 edge-disjoint Hamilton cycles.

This conjecture would simultaneously generalize the Hamilton decomposition and Hamilton cycle-packing results discussed in the paper, and would give a best-possible bound for each graph rather than only for graphs with a prescribed minimum-degree class. The source records that it was proved for δ≥(2−2+ε)n\delta\ge(2-\sqrt{2}+\varepsilon)n, so the full statement remains open in the supplied context.

References

Primary source

Béla Csaba, Daniela Kühn, Allan Lo, Deryk Osthus and Andrew Treglown, “Proof of the 1-factorization and Hamilton Decomposition Conjectures”, arXiv:1401.4159 (2014).

Additional references

2 papers in this index state this conjecture (2009–2014). The statement above is taken from the most recent of them; the others are arXiv:0908.3411.

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.