coloring of $K_n$, there is a rainbow path of length $$\left(\frac{3}{4}-o(1)\right)n\text.$$

Several theorems and conjectures on rainbow cycles can be found in a paper by Akbari, Etesami, Mahini and Mahmoody [@Akbari2007]. Most importantly (for our purposes), it is proved that in every proper edge coloring of $K_n$, there is a rainbow cycle of length at least $n/2-1$. This result was later improved on by Gyárfás, Ruszinkó, Sarközy and Schelp in [@Gyarfas2011], where a bound of $(4/7-o(1))n$ is given.

A related topic is that of colorful Hamiltonian cycles in proper edge colorings of $K_n$. In [@Akbari2007], it is conjectured that every proper edge coloring of $K_n$ contains a Hamiltonian cycle using at least $n-2$ colors, and it is proved that there is always one with at least $(2/3-o(1))n$ colors. The construction used in our proof of Theorem \[thm:intro\] can be used to show that there are Hamiltonian cycles using at least $(3/4-o(1))n$ colors.

In [@Hahn1986], Hahn and Thomassen studied rainbow cycles and paths in *$k$-bounded edge colorings* of $K_n$, that is, (not necessarily proper) edge colorings that use every color at most $k$ times. It is shown that for fixed $k$ and large enough $n$, every such coloring contains a Hamiltonian 