2010/05/21 by Tomasz Łuczak, Miklós Simonovits, Łuczak, Tomasz +3
Mathematics · #05C55 #Combinatorics (math.CO) #FOS: Mathematics #math.CO #msc:05C55
paper · pdf · doi:10.48550/arxiv.1005.3926
8 pages, 0 figures Added references. Corrected typos
arxiv created 2010/08/24 · arxiv updated 2010/08/25
For a graph L and an integer k≥ 2, Rk(L) denotes the smallest integer N for which for any edge-colouring of the complete graph KN by k colours there exists a colour i for which the corresponding colour class contains L as a subgraph. Bondy and Erdős conjectured that for an odd cycle Cn on n vertices, Rk(Cn) = 2k-1(n-1)+1 for n>3. 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, Rk(Cn)≤ k2kn+o(n), as n→∞. When n is even, Yongqi, Yuansheng, Feng, and Bingxi gave a construction, showing that Rk(Cn)≥ (k-1)n-2k+4. Here we prove that if n is even, then Rk(Cn)≤ kn+o(n), as n→∞.