The regular-subgraph conjecture for Hamilton-cycle packings

Let GG be a graph on nn vertices, and let regeven(G)\operatorname{reg}_{\operatorname{even}}(G) denote the largest degree of an even-regular spanning subgraph of GG. The regular-subgraph conjecture. If

δ(G)n2,\delta(G)\ge \frac{n}{2},

then GG contains at least

regeven(G)2\frac{\operatorname{reg}_{\operatorname{even}}(G)}{2}

edge-disjoint Hamilton cycles. This graph-by-graph strengthening of the preceding conjecture is best possible for each individual graph. It was proved when δ(22+ε)n\delta\ge(2-\sqrt{2}+\varepsilon)n, but remains open in general.

Sources & referencesView supporting material

Primary source

Daniela Kühn, John Lapinskas and Deryk Osthus, “Optimal packings of Hamilton cycles in graphs of high minimum degree”, arXiv:1211.3263 (2012).

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.