zbMATH — the first resource for mathematics

Multicoloured Hamilton cycles. (English) Zbl 0817.05028
Electron. J. Comb. 2, Research paper R10, 13 p. (1995); printed version J. Comb. 2, 165-177 (1995).
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 G. Hahn and 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.

05C15 Coloring of graphs and hypergraphs
05C38 Paths and cycles
05C45 Eulerian and Hamiltonian graphs
05C20 Directed graphs (digraphs), tournaments
Full Text: EMIS EuDML