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

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(n3∕4) vertices, by...

Full description

Saved in:
Bibliographic Details
Published in:European journal of combinatorics 2019-06, Vol.79, p.140-151
Main Authors: Balogh, József, Molla, Theodore
Format: Article
Language:English
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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(n3∕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.
ISSN:0195-6698
1095-9971
DOI:10.1016/j.ejc.2019.02.008