The 3-colored Ramsey number of even cycles

Author(s)

Benevides, Fabricio Siqueira ^{[1, 2]} ; Skokan, Jozef ^{[3, 4]}

Affiliation

^[1] Univ Sao Paulo, Inst Matemat & Estat, BR-05508090 Sao Paulo - Brazil

^[2] Univ Memphis, Memphis, TN 38152 - USA

^[3] London Sch Econ, Dept Math, London WC2A 2AE - England

^[4] Univ Illinois, Dept Math, Urbana, IL 61801 - USA

• Document type: Journal article
• Source: JOURNAL OF COMBINATORIAL THEORY SERIES B; v. 99, n. 4, p. 690-708, JUL 2009.
• Web of Science Citations: 19

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 Erdos conjectured that when L is the cycle C(n) on n vertices, R(C(n), C(n), C(n)) = 4n - 3 for every odd n > 3. Luczak proved that if n is odd, then R(C(n), C(n), C(n)) = 4n + o(n), as n -> infinity, and Kohayakawa, Simonovits and Skokan confirmed the Bondy-Erdos conjecture for all sufficiently large values of n. Figaj and Luczak determined an asymptotic result for the `complementary' case where the cycles are even: they showed that for even n, we have R(C(n), C(n), C(n)) = 2n + o(n), as n -> infinity. In this paper, we prove that there exists n I such that for every even n >= n(1), R(C(n), C(n), C(n)) = 2n. (C) 2009 Elsevier Inc. All rights reserved. (AU)

• FAPESP's process: 03/09925-5 - Foundations of computer science: combinatory algorithms and discrete structures
• Grantee: Yoshiharu Kohayakawa
• Support Opportunities: PRONEX Research - Thematic Grants