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 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 Hamiltonian 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 − 2 n of Andersen.