Cycles Avoiding a Color in Colorful Graphs. Issue 4 (14th April 2015)

• Record Type: Journal Article
• Authors: Meierling, Dirk; Müttel, Janina; Rautenbach*, Dieter
• Is Part Of: Journal of graph theory. Volume 81:Issue 4(2016)
• Page Start: 342
• Page End: 350
• Publication Date: 2015-04-14
• Subjects: Ramsey numbers -- cycles -- 05C38 -- 05C55; Graph theory -- Periodicals; 511
• DOI: 10.1002/jgt.21879
• Languages: English
• ISSNs: 0364-9024

Abstract

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 .