Ramsey number of a cycle versus a graph of a given size
Abstract
In this paper, we prove that for every $k$ and every graph $H$ with $m$ edges and no isolated vertices, the Ramsey number $R(C_k,H)$ is at most $2m+\lfloor \frac{k-1}{2} \rfloor$, provided $m$ is sufficiently large with respect to $k$. This settles a problem of Erdős, Faudree, Rousseau and Schelp.
Fields of Study & Subjects
Limits and Structures in Graph Theory
Advanced Combinatorial Mathematics
Analytic Number Theory Research
Publication details
- Journal / source
- arXiv (Cornell University)
- Publication date
- 15 January 2026
- Document type
- Preprint