Cycles Avoiding a Color in Colorful Graphs. Issue 4 (14th April 2015) - Meierling, Dirk
Abstract: The Ramsey numbers of cycles imply that every 2‐edge‐colored complete graph on n vertices contains monochromatic cycles of all lengths between 4 and at least 2 3 n . We generalize this result to k ≥ 3 colors by showing that every k ‐edge‐colored complete graph on n ≥ 6 vertices contains ( k − 1 ) ‐edge‐colored cycles of all lengths between 3 and at least ( 2 k − 2 2 k − 1 − 2 k − 4 n ) n .