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(lognn) 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((logn) 2 ) different colors appear. For large n, this is an improvement of the previous best known lower bound of n−2n of Andersen.
ASJC Scopus subject areas
- Discrete Mathematics and Combinatorics