\magnification=1440
\font\bigtenrm=cmr10 scaled\magstep4

Abstract for Michael Albert, Alan Frieze and Bruce Reed,\break
 Multicoloured Hamilton Cycles

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. 
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 $t|n$ then the vertices can be partitioned into
$n/t$ $t-$sets $K_1,K_2,\ldots,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\H{o}s and Spencer's modification of
the Local Lemma.

\bye

.
