Near-rainbow Hamilton cycle conjecture for properly coloured Dirac graphs

From papers

Let GG be a Dirac graph on nn vertices, meaning a graph with minimum degree at least n/2n/2, and let its edge-colouring be proper if every pair of incident edges receives different colours. A Hamilton cycle is rainbow if all its edges receive distinct colours, and it has rr distinct colours when the set of colours on its edges has size rr. Near-rainbow Hamilton cycle conjecture. Every proper edge-colouring of a Dirac graph on nn vertices contains a Hamilton cycle with at least n/2o(n)n/2-o(n) distinct colours. This asks for a linear lower bound without any global boundedness assumption; the supplied source gives no resolution.

Progress summary

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

Sources & referencesView supporting material

Primary source

Danni Peng and Zhifei Yan, “Near rainbow Hamilton cycles in dense graphs”, arXiv:2411.18743 (2024).

Solutions 0

No solutions have been posted yet.