Article ID Journal Published Year Pages File Type
4657095 Journal of Combinatorial Theory, Series B 2009 19 Pages PDF
Abstract

Denote by R(L,L,L) the minimum integer N such that any 3-coloring of the edges of the complete graph on N vertices contains a monochromatic copy of a graph L. Bondy and Erdős conjectured that when L is the cycle Cn on n vertices, R(Cn,Cn,Cn)=4n−3 for every odd n>3. Łuczak proved that if n is odd, then R(Cn,Cn,Cn)=4n+o(n), as n→∞, and Kohayakawa, Simonovits and Skokan confirmed the Bondy–Erdős conjecture for all sufficiently large values of n.Figaj and Łuczak determined an asymptotic result for the ‘complementary’ case where the cycles are even: they showed that for even n, we have R(Cn,Cn,Cn)=2n+o(n), as n→∞. In this paper, we prove that there exists n1 such that for every even n⩾n1, R(Cn,Cn,Cn)=2n.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics