Premium
Cycles Avoiding a Color in Colorful Graphs
Author(s) -
Meierling Dirk,
Müttel Janina,
Rautenbach* Dieter
Publication year - 2016
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.21879
Subject(s) - combinatorics , colored , monochromatic color , mathematics , graph , enhanced data rates for gsm evolution , complete graph , wheel graph , discrete mathematics , graph power , line graph , computer science , physics , artificial intelligence , materials science , optics , composite material
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 least2 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 .
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom