Problem Statement
Let $R(G;3)$ 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(C_n;3) \leq 4n-3.\]
Categories:
Graph Theory Ramsey Theory
Progress
A problem of Bondy and Erdős. This inequality is best possible for odd $n$.Luczak [Lu99] has shown that $R(C_n;3)\leq (4+o(1))n$ for all $n$, and in fact $R(C_n;3)\leq 3n+o(n)$ for even $n$.
Kohayakawa, Simonovits, and Skokan [KSS05] proved this conjecture when $n$ is sufficiently large and odd. Benevides and Skokan [BeSk09] proved that if $n$ is sufficiently large and even then $R(C_n;3)=2n$.
This problem is #25 in Ramsey Theory in the graphs problem collection.
Source: erdosproblems.com/556 | Last verified: January 15, 2026