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

##### MSC:
 05C15 Coloring of graphs and hypergraphs 05C38 Paths and cycles 05C45 Eulerian and Hamiltonian graphs 05C20 Directed graphs (digraphs), tournaments
##### Keywords:
complete graph; colour; Hamiltonian cycle; digraph
Full Text: