Problem 555

Let $R_k(G)$ denote the minimal $m$ such that if the edges of $K_m$ are $k$ -coloured then there is a monochromatic copy of $G$ . Determine the value of

R_k(C_{2n}).

Source: erdosproblems.com/555

Graph theory
Ramsey theory

Wiki page

Status

Open

No claim settles this problem.

Open, in the site's label (OPEN; page last edited 8 February 2026, accessed 2026-09-17). No source determines $R_k(C_{2n})$ for general $k$ and $n$ , and the search, whose scope the Current assessment records, found no proof claim; the problem has no claim page and its frontmatter standing is open. What is known: exact values for two colors (all $n\ge3$ ) and for three colors and large $n$ ; for fixed $k\ge4$ and large $n$ the linear bracket $(k-1)(2n-2)+2\le R_k(C_{2n})\le (k-\frac14)2n+o(n)$ from sources read here, improved to the coefficient $k-\frac12$ in a later paper not held; for fixed $n$ and growing $k$ the polynomial bracket $k^{1+1/2n}\ll R_k(C_{2n})\ll k^{1+(1+\varepsilon)/(n-1)}$ , whose upper exponent is the truth, $R_k(C_{2n})=\Theta(k^{n/(n-1)})$ , for $n\in\{2,3,5\}$ by a refereed paper [LiLih09]; and for $C_4$ the bracket $k^2+2\le R_k(C_4)\le k^2+k+1$ for prime powers $k$ . This is a bounded negative finding, not a certificate of openness.

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 (1981), 9--17. Site source key; its pages 9--14 do not state the question or the bounds (p. 13 records the two-color determination and the three-color conjecture). Library home: Erdős 1981.
ErGr75: Erdős, P. and Graham, R. L., On partition theorems for finite graphs. Colloq. Math. Soc. János Bolyai 10 (1975), 515--527; Theorems 5 and 6, pp. 521--522, and the $C_4$ statement, p. 523. Library home: Erdős and Graham 1975.
ChGr75: Chung, F. R. K. and Graham, R. L., On multicolor Ramsey numbers for complete bipartite graphs. J. Combin. Theory Ser. B 18 (1975), 164--169, DOI 10.1016/0095-8956(75)90043-X. Theorem 3 and Corollary 1, p. 166, with the proof of Theorem 3 on p. 167; the paper is in the publisher's open archive. Library home: Chung and Graham 1975; result pages Theorem 3 and Corollary 1.
DJR17: Davies, E., Jenssen, M. and Roberts, B., Multicolour Ramsey numbers of paths and even cycles. European J. Combin. 63 (2017), 124--133, DOI 10.1016/j.ejc.2017.03.002; arXiv:1606.00762v3 (23 February 2017). Theorem 2 and the introduction, p. 2. Library home: Davies and Roberts 2017.
KnSu19: Knierim, C. and Su, P., Improved bounds on the multicolor Ramsey numbers of paths and even cycles. arXiv:1801.04128 (12 January 2018); Electron. J. Combin., DOI 10.37236/7614. Not held; known here through its arXiv abstract.
YYFB06: Yongqi, S., Yuansheng, Y., Feng, X. and Bingxi, L., New lower bounds on the multicolor Ramsey numbers $R_r(C_{2m})$ . Graphs Combin. 22 (2006), 283--288, DOI 10.1007/s00373-006-0659-y. Not held; its bound is quoted from the publisher's abstract and from [DJR17] p. 2.
BeSk09: Benevides, F. S. and Skokan, J., The 3-colored Ramsey number of even cycles. J. Combin. Theory Ser. B 99 (2009), 690--708; the copy read is the CDAM research report LSE-CDAM-2008-17 (2008). Theorem 1. Library home: Benevides and Skokan 2009.
BoEr73: Bondy, J. A. and Erdős, P., Ramsey numbers for cycles in graphs. J. Combin. Theory Ser. B 14 (1973), 46--54; the note added in proof, pp. 53--54, records the two-color formula of Faudree and Schelp and of Rosta. Library home: Bondy and Erdős 1973.
FaSc74: Faudree, R. J. and Schelp, R. H., All Ramsey numbers for cycles in graphs. Discrete Math. 8 (1974), 313--329, DOI 10.1016/0012-365X(74)90151-4. Not held; quoted second-hand from [BoEr73] and [JeSk21].
Ro73: Rosta, V., On a Ramsey-type problem of J. A. Bondy and P. Erdős, I, II. J. Combin. Theory Ser. B 15 (1973), 94--104 and 105--120, DOIs 10.1016/0095-8956(73)90035-X and 10.1016/0095-8956(73)90036-1. Not held; quoted second-hand as for [FaSc74].
JeSk21: Jenssen, M. and Skokan, J., Exact Ramsey numbers of odd cycles via nonlinear optimisation. Adv. Math. 376 (2021), Paper No. 107444; arXiv:1608.05705v1. Context: its p. 2 displays the two-color cycle values. Library home: Jenssen 2021.
LiLih09: Li, Y. and Lih, K.-W., Multi-color Ramsey numbers of even cycles. European J. Combin. 30 (2009), 114--118, DOI 10.1016/j.ejc.2008.02.008. Theorem 1, p. 115, with Lemma 1 (p. 115), the bound (2) (p. 114) and Lemma 5 (p. 118); the paper is in the publisher's open archive. Library home: Li and Lih 2009; result page Theorem 1.
Tar24: Taranchuk, V., A new lower bound for the multicolor Ramsey number $r_k(K_{2,t+1})$ . arXiv:2411.14364 (v1 21 November 2024; v2 23 November 2024). Preprint; Theorem 1.3, p. 3, and the Lazebnik--Woldar bound restated on p. 2. Library home: Taranchuk 2024.

Problem 555

Status

Proof claims

Discussion