Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí toán học quốc tế đề tài: MULTICOLOURED HAMILTON CYCLES. | MULTICOLOURED HAMILTON CYCLES Michael Albert Alan Frieze and Bruce Reed Department of Mathematics Carnegie-Mellon University Pittsburgh Submitted April 25th 1995 Accepted May 9th 1995 Abstract The edges of the complete graph Kn are coloured so that no colour appears more than cn 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 7 . We prove a similar result for the complete digraph with c 1 64. We also show by essentially the same technique that if t 3 c 2t2 1 t -1 no colour appears more than cn times and t n then the vertices can be partitioned into n t t sets K1 K2 . Kn t such that the colours of the n t 1 2 edges contained in the Kj s are distinct. The proof technique follows the lines of Erdos and Spencer s 2 modification of the Local Lemma 1 . Current address of Bruce Reed Equipe Combinatoire CNRS Université Pierre et Marie Curie 4 Place Jussieu Paris France t Alan Frieze partially supported by NSF grant CCR-9225008 1 THE ELECTRONIC .JOURNAL OF COMBINATORICS 2 1995 R10 2 1 Introduction Let the edges of the complete graph Kn be coloured so that no colour is used more than k k n times. We refer to this as a k-bounded colouring. We say that a subset of the edges of Kn is multicoloured if each edge is of a different colour. We say that the colouring is H-good if a multi-coloured Hamilton cycle exists . one with a multi-coloured edge-set. Clearly the colouring is H-good if k 1 and may not be if k n 2 since then we may only use n 1 colours. The main question we address here then is that of how fast can we allow k to grow and still guarantee that a k-bounded colouring is H-good. The problem is mentioned in Erdos Nestril and Rodl 3 . There they mention it as an Erdos - Stein problem and show that k can be any constant. Hahn and Thomassen 7 were the next people to consider this problem and they showed that k
