Alternating Hamiltonian cycles

Colour the edges of a complete graph withn vertices in such a way that no vertex is on more thank edges of the same colour. We prove that for everyk there is a constantc _ksuch that ifn>c _kthen there is a Hamiltonian cycle with adjacent edges having different colours. We prove a number of other results in the same vein and mention some unsolved problems.