Multicoloured Hamilton cycles
type: Item
instance of: scholarly article
title: Multicoloured Hamilton cycles
zbMATH Open document ID: 0817.05028
published in: The Electronic Journal of Combinatorics
publication date: 1995-05-22T00:00:00Z
full work available at URL: https://eudml.org/doc/118618
full work available at URL: R10
review text: 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.
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 05C45
Mathematics Subject Classification ID: 05C20
zbMATH DE Number: 757853
zbMATH Keywords: complete graph
zbMATH Keywords: colour
zbMATH Keywords: Hamiltonian cycle
zbMATH Keywords: digraph
author: Michael Albert
author: Alan Frieze
author: Bruce Reed
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 757853