Problem 570

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?

Source: erdosproblems.com/570

Graph theory
Ramsey theory

Wiki page

Status

SolvedProved

An accepted solution exists. The statement is true.

The site labels the problem PROVED (page last edited 16 January 2026, accessed 2026-09-08), and CFMPP26 states the eventual bound for every $k$ . The direct primary-source coverage is incomplete only at $k=5$ , as explained below. The claim pages record the results behind the label with their postings and acceptance evidence: Sidorenko 1993 and Goddard and Kleitman 1994 for $k=3$ , Erdős, Faudree, Rousseau and Schelp 1993 for even $k$ , Jayawardene 1999 for $k=5$ (second-hand, the thesis unread), and Cambie, Freschi, Morawski, Petrova and Pokrovskiy 2026 for odd $k\ge7$ and the whole statement, accepted on the site curator's record since the preprint is not refereed; the frontmatter standing derives from these pages.

CFMPP26: S. Cambie, A. Freschi, P. Morawski, K. Petrova, and A. Pokrovskiy, Ramsey number of a cycle versus a graph of a given size. arXiv:2601.10238 (2026).
EFRS93: Erdős, Paul and Faudree, R. J. and Rousseau, C. C. and Schelp, R. H., Ramsey size linear graphs. Combin. Probab. Comput. (1993), 389-399.
GoKl94: Goddard, Wayne and Kleitman, Daniel J., An upper bound for the Ramsey numbers $r(K_3,G)$ . Discrete Math. (1994), 177-182.
Ja99: C. J. Jayawardene, Ramsey numbers related to small cycles. University of Memphis (1999).
Si91: Sidorenko, A. F., An upper bound on the Ramsey number $r(K_3,G)$ depending only on the size of the graph $G$ . J. Graph Theory (1991), 15-17. The site's key names this 1991 note, which gives a weaker bound; the $k=3$ result credited to Sidorenko on the claim page is the 1993 paper below.
Si93: Sidorenko, A. F., The Ramsey number of an $n$ -edge graph versus triangle is at most $2n+1$ . J. Combin. Theory Ser. B 58 (1993), 185-196, doi:10.1006/jctb.1993.1036. Not held.

Problem 570

Status

Proof claims

Discussion