×

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
Full Text: EMIS EuDML