Premium
On the multi‐colored Ramsey numbers of cycles
Author(s) -
Łuczak Tomasz,
Simonovits Miklós,
Skokan Jozef
Publication year - 2012
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.20572
Subject(s) - combinatorics , mathematics , conjecture , integer (computer science) , ramsey's theorem , graph , colored , upper and lower bounds , image (mathematics) , discrete mathematics , mathematical analysis , materials science , artificial intelligence , computer science , composite material , programming language
For a graph L and an integer k ≥2, R k ( L ) denotes the smallest integer N for which for any edge‐coloring of the complete graph K N by k colors there exists a color i for which the corresponding color class contains L as a subgraph. Bondy and Erdos conjectured that, for an odd cycle C n on n vertices,They proved the case when k = 2 and also provided an upper bound R k ( C n )≤( k + 2)! n . Recently, this conjecture has been verified for k = 3 if n is large. In this note, we prove that for every integer k ≥4,When n is even, Sun Yongqi, Yang Yuansheng, Xu Feng, and Li Bingxi gave a construction, showing that R k ( C n )≥( k −1) n −2 k + 4. Here we prove that if n is even, then© 2011 Wiley Periodicals, Inc. J Graph Theory 69: 169‐175, 2012