Problem Statement
Let $k\geq 3$. Is it true that, for any graph $H$ on $m$ edges without isolated vertices,\[R(C_k,H) \leq 2m+\left\lceil\frac{k-1}{2}\right\rceil?\]
Categories:
Graph Theory Ramsey Theory
Progress
This was proved for even $k$ by Erdős, Faudree, Rousseau, and Schelp [EFRS93]. It was proved for $k=3$ by Sidorenko [Si93].See also the entry in the graphs problem collection.
Source: erdosproblems.com/570 | Last verified: January 15, 2026