On Rainbow Cycles in Edge Colored Complete Graphs

In this paper we consider optimal edge colored complete graphs. We show that in any optimal edge coloring of the complete graph Kn, there is a Hamil-ton cycle with at most √ 8n different colors. We also prove that in every proper edge coloring of the complete graph Kn, there is a rainbow cycle with at least n/2−1 colors (A rainbow cycle is a cycle whose all edges have different colors). We show that for sufficiently large n, the expected number of different colors appearing on a random Hamilton cycle is approximately (1 − e −1)n for any optimal edge coloring of Kn. Finally it is proved that if Kn is colored using an abelian group of odd order n, then it has a rainbow Hamilton cycle