Long rainbow cycles and Hamiltonian cycles using many colors in properly edge-colored complete graphs

Abstract

We prove two results regarding cycles in properly edge-colored graphs. First, we make a small improvement to the recent breakthrough work of Alon, Pokrovskiy and Sudakov who showed that every properly edge-colored complete graph $G$ on $n$ vertices has a rainbow cycle on at least $n-O(n^{3/4})$ vertices, by showing that $G$ has a rainbow cycle on at least $n-O(\log n\sqrt{n})$ vertices. Second, by modifying the argument of Hatami and Shor which gives a lower bound for the length of a partial transversal in a Latin Square, we prove that every properly colored complete graph has a Hamilton cycle in which at least $n-O((\log n{)}^2)$ different colors appear. For large $n$, this is an improvement of the previous best known lower bound of $n-\sqrt{2n}$ of Andersen.

12 pages