Hahn's rainbow Hamilton path conjecture

Let KnK_n be the complete graph on nn vertices. An edge-colouring is kk-bounded if no colour appears on more than kk edges. A subgraph is rainbow if no two of its edges have the same colour. Hahn's conjecture. Any (n/2)(n/2)-bounded colouring of E(Kn)E(K_n) contains a rainbow Hamilton path. The conjecture was disproved by Maamoun and Meyniel, who showed that it fails even for proper colourings of K2tK_{2^t} when t2t\geq 2.

Sources & referencesView supporting material

Primary source

Matthew Coulson and Guillem Perarnau, “A Rainbow Dirac's Theorem”, arXiv:1809.06392 (2018).

Additional references

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

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.