Near-rainbow Hamilton cycle conjecture for properly coloured Dirac graphs

About 2 years old · traced to

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/2−o(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.

References

Primary source

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

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.