OPEN
This is open, and cannot be resolved with a finite computation.
Let $R(G;k)$ 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(C_{2n};k).\]
A problem of Erdős and Graham. Erdős
[Er81c] gives the bounds\[k^{1+\frac{1}{2n}}\ll R(C_{2n};k)\ll k^{1+\frac{1}{n-1}}.\]Chung and Graham
[ChGr75] showed that\[R(C_4;k)>k^2-k+1\]when $k-1$ is a prime power and\[R(C_4;k)\leq k^2+k+1\]for all $k$.
This problem is
#24 in Ramsey Theory in the graphs problem collection.
View the LaTeX source
When referring to this problem, please use the original sources of Erdős. If you wish to acknowledge this website, the recommended citation format is:
T. F. Bloom, Erdős Problem #555, https://www.erdosproblems.com/555, accessed 2026-01-16
