On the multi‐colored Ramsey numbers of cycles |
| |
| Authors: | Tomasz Łuczak Miklós Simonovits Jozef Skokan |
| |
| Institution: | 1. Faculty of Mathematics and Computer Science, Adam Mickiewicz University 61‐614 Pozna?, Poland;2. Alfréd Rényi Institute of Mathematics Hungarian Academy of Sciences H‐1053 Budapest, Reáltanoda u. 13‐15, Hungary;3. Department of Mathematics, London School of Economics, Houghton Street London Wc2a 2ae, United Kingdom |
| |
| Abstract: | For a graph L and an integer k≥2, Rk(L) denotes the smallest integer N for which for any edge‐coloring of the complete graph KN 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 Cn on n vertices,  They proved the case when k = 2 and also provided an upper bound Rk(Cn)≤(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 Rk(Cn)≥(k?1)n?2k+ 4. Here we prove that if n is even, then  © 2011 Wiley Periodicals, Inc. J Graph Theory 69: 169‐175, 2012 |
| |
| Keywords: | |
|
|
