Problem 556

Let $R_3(G)$ denote the minimal $m$ such that if the edges of $K_m$ are $3$ -coloured then there must be a monochromatic copy of $G$ . Show that

R_3(C_n) \leq 4n-3.

Second statement

Let $R_3(G)$ denote the minimal $m$ such that if the edges of $K_m$ are $3$ -coloured then there must be a monochromatic copy of $G$ . Show that for every $n>3$

R_3(C_n) \leq 4n-3.

Source: erdosproblems.com/556

Graph theory
Ramsey theory

Wiki page

Status

Open

No claim settles this problem.

Decidable, in the site's label (page last edited 8 February 2026), which the site defines as resolved up to a finite check; the label describes the corrected Statement, which excludes $n=3$ . The frontmatter standing, derived from the claim pages, judges the corrected Statement and is open: the partial claim pages Kohayakawa, Simonovits and Skokan 2005 and Jenssen and Skokan 2016 cover all large odd $n$ , and Benevides and Skokan 2008 all large even $n$ , while the $n$ from $9$ up to the two unnamed thresholds remain open. The Benevides--Skokan and Jenssen--Skokan pages are accepted on their refereed journal publications; the Kohayakawa--Simonovits--Skokan page is claimed, since its full proof is an unrefereed research report and its proceedings abstract is not shown to have been refereed. The curator's credit to Kohayakawa, Simonovits and Skokan and to Benevides and Skokan is recorded on their pages and is not acceptance evidence, because the site's label DECIDABLE does not mark the problem settled.

Notes

The site's wording quantifies over every cycle length $n\ge3$ and fails at $n=3$ : $C_3=K_3$ , so $R_3(C_3)=R(3,3,3)$ , which is $17>9=4\cdot3-3$ . The strict inequality $R(3,3,3)>9$ is elementary: two copies of the two-colored $K_5$ without a monochromatic triangle (the pentagon in one color, the pentagram in the other), joined by all crossing edges in the third color, give a $3$ -coloring of $K_{10}$ with no monochromatic triangle, checked over all $120$ triples, so $R(3,3,3)\ge11$ . A comment of 13 July 2026 by KentaKitamura in the site's discussion thread records the same failure. It is the only recorded failure: the values listed in OEIS A389335 give the inequality for $4\le n\le8$ , and the theorems below give it for all large $n$ . The change inserts the words "for every $n>3$ " before the display; nothing else changes. The defect is already in the poser's text: Erdős's own statements of the conjecture, [Er81] Part V, display (3), p. 9 of the re-typeset copy, and [Er81c] display (15), printed p. 13, print $r(C_n,C_n,C_n)\le4n-3$ with no restriction on $n$ , and each adds only that the bound, if true, is best possible for odd $n$ ; the site reproduces that wording. The threshold is the literature's statement of the conjecture as Bondy and Erdős's: [KSS05] p. 2, display (2), "Bondy and Erdős [4] conjectured that if $n>3$ is odd, then $R(C_n,C_n,C_n)=4n-3$ ", and [BeSk09] p. 2, display (1), which states the same equality for odd $n>3$ ; both papers settle only large $n$ , so neither settles the corrected Statement. The corrected Statement is a combined form: the literature's " $n>3$ ", kept for even $n$ as Erdős's bound and the site's are; it is the form OEIS A389335 prints, " $a(n)\le4n-3$ for $n\ge4$ ". The form rests on these sources alone, not on which results settle it. The one result about the site's wording alone is the value $R(3,3,3)=17$ of R. E. Greenwood and A. M. Gleason, Combinatorial relations and chromatic graphs, Canad. J. Math. 7 (1955), 1--7, doi:10.4153/CJM-1955-001-4; it is correct, but it answers the site's wording (every $n\ge3$ ), not the corrected Statement (every $n>3$ ), so it does not count toward the problem's standing; it is credited here and on its rejected claim page, Greenwood and Gleason 1955. The problem's standing judges the corrected Statement.

BoEr73: Bondy, J. A. and Erdős, P., Ramsey numbers for cycles in graphs. J. Combinatorial Theory Ser. B 14 (1973), no. 1, 46--54, doi:10.1016/S0095-8956(73)80005-X; Section 4, p. 53. Library home: Bondy and Erdős 1973.
KSS05: Kohayakawa, Y., Simonovits, M. and Skokan, J., The 3-colored Ramsey number of odd cycles. Proceedings of GRACO2005, Electron. Notes Discrete Math. 19 (2005), 397--402, doi:10.1016/j.endm.2005.05.053 (an extended abstract); the full proof is CDAM Research Report LSE-CDAM-2008-16 (38 pages), whose pages and statement numbers are used here: Theorem 1, p. 2; Claim 2, p. 4; Theorem 3, p. 5. Library home: Kohayakawa and Skokan 2005.
BeSk09: Benevides, F. S. and Skokan, J., The 3-colored Ramsey number of even cycles. J. Combin. Theory Ser. B 99 (2009), no. 4, 690--708, doi:10.1016/j.jctb.2008.12.002; locators are those of CDAM Research Report LSE-CDAM-2008-17 (22 pages): Theorem 1, p. 2; Lemma 2, p. 3. Library home: Benevides and Skokan 2009.
JeSk21: Jenssen, M. and Skokan, J., Exact Ramsey numbers of odd cycles via nonlinear optimisation. Adv. Math. (2021), Paper No. 107444, 46 pp.; arXiv:1608.05705. Theorem 1.2: $R_k(C_n)=2^{k-1}(n-1)+1$ for fixed $k\ge2$ and all sufficiently large odd $n$ ; its $k=3$ case is the odd half of this problem for large $n$ . Library home: Jenssen 2021; result page Theorem 1.2.
Lu99: Łuczak, T., $R(C_n,C_n,C_n)\leq(4+o(1))n$ . J. Combin. Theory Ser. B 75 (1999), no. 2, 174--187, doi:10.1006/jctb.1998.1874. Its abstract and its zbMATH review (Zbl 0934.05091) state the bound $(4+o(1))n$ for every $n$ , asymptotically sharp for odd $n$ ; [KSS05] (3) and [BeSk09] p. 2 quote the odd case.
LSS12: Łuczak, T., Simonovits, M. and Skokan, J., On the multi-colored Ramsey numbers of cycles. J. Graph Theory 69 (2012), 169--175; arXiv:1005.3926. Cited from its abstract: bounds for $k\ge4$ colors, adjacent to this problem.
Er81: Erdős, P., On the combinatorial problems which I would most like to see solved. Combinatorica 1 (1981), 25--42. Site source key; Part V, display (3), p. 9 of the re-typeset copy. Library home: Erdős 1981.
Er81c: Erdős, P., Some new problems and results in graph theory and other branches of combinatorial mathematics. Combinatorics and graph theory (Calcutta, 1980), Lecture Notes in Math. 885, Springer (1981), 9--17; display (15), printed p. 13. Library home: Erdős 1981.
OEIS: Beregovsky, E., Sequence A389335, The On-Line Encyclopedia of Integer Sequences (2025), https://oeis.org/A389335, accessed 2026-09-17: $R(C_n,C_n,C_n)$ for $n=3,\ldots,8$ , with the conjecture stated as " $a(n)\le4n-3$ for $n\ge4$ " and Radziszowski's survey among its links.

Problem 556

Second statement

Status

Notes

Proof claims

Discussion