Multicoloured Hamilton cycles (Q1890827): Difference between revisions

Summary: The edges of the complete graph \(K_ n\) are coloured so that no colour appears more than \(\lceil cn\rceil\) times, where \(c< 1/32\) is a constant. We show that if \(n\) is sufficiently large then there is a Hamiltonian cycle in which each edge is a different colour, thereby proving a 1986 conjecture of Hahn and Thomassen, see \textit{G. Hahn} and \textit{C. Thomassen} [Discrete Math. 62, 29-33 (1986; Zbl 0613.05044)]. We prove a similar result for the complete digraph with \(c< 1/64\). We also show, by essentially the same technique, that if \(t\geq 3\), \(c< (2t^ 2(1+ t))^{-1}\), no colour appears more than \(\lceil cn\rceil\) times and if \(t| n\) then the vertices can be partitioned into \(n/t\) \(t\)-sets \(K_ 1,K_ 2,\dots, K_{n/t}\) such that the colours of the \(n(t- 1)/2\) edges contained in the \(K_ i\)'s are distinct. The proof technique follows the lines of Erdős and Spencer's modification of the local lemma.