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

József Balogh, Theodore Molla

Research output: Contribution to journalArticlepeer-review

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(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.

Original languageEnglish (US)
Pages (from-to)140-151
Number of pages12
JournalEuropean Journal of Combinatorics
Volume79
DOIs
StatePublished - Jun 2019

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics

Fingerprint Dive into the research topics of 'Long rainbow cycles and Hamiltonian cycles using many colors in properly edge-colored complete graphs'. Together they form a unique fingerprint.

Cite this