PROVED
This has been solved in the affirmative.
Let $k\geq 3$. Is it true that, if $m$ is sufficiently large, for any graph $H$ on $m$ edges without isolated vertices,\[R(C_k,H) \leq 2m+\left\lfloor\frac{k-1}{2}\right\rfloor?\]
This is Question 5 of
[EFRS93]. This was proved for even $k$ by Erdős, Faudree, Rousseau, and Schelp
[EFRS93].
This was proved for $k=3$ independently by Goddard and Kleitman
[GoKl94] and Sidorenko
[Si91]. This was proved for $k=5$ by Jayawardene
[Ja99]. Finally it was proved for all odd $k\geq 7$ by Cambie, Freschi, Morawski, Petrova, and Pokrovskiy
[CFMPP26].
This problem is
#35 in Ramsey Theory in the graphs problem collection.
View the LaTeX source
This page was last edited 16 January 2026. View history
|
Likes this problem
|
None
|
|
Interested in collaborating
|
None
|
|
Currently working on this problem
|
None
|
|
This problem looks difficult
|
None
|
|
This problem looks tractable
|
None
|
|
The results on this problem could be formalisable
|
None
|
|
I am working on formalising the results on this problem
|
None
|
Additional thanks to: Stijn Cambie
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 #570, https://www.erdosproblems.com/570, accessed 2026-04-11
