Rainbow Hamilton cycle conjecture for bounded edge-colourings of 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. The colouring is n/8n/8-bounded if each colour is assigned to at most n/8n/8 edges. A Hamilton cycle is rainbow if all its edges receive distinct colours. Rainbow Hamilton cycle conjecture. There exists a rainbow Hamilton cycle in any proper n/8n/8-bounded edge-colouring of a Dirac graph on nn vertices. The paper proves near-rainbow results and shows that the constant 1/81/8 is best possible up to lower-order terms, leaving the exact n/8n/8-bounded assertion open.

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).

Additional references

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

Solutions 0

No solutions have been posted yet.