Problem Statement
Let $G$ be a graph such that $R(G,T_n)\ll n$ for any tree $T_n$ on $n$ vertices and $R(G,K_n)\ll n^2$. Is it true that, for any $H$ with $m$ edges and no isolated vertices,\[R(G,H)\ll m?\]
Categories:
Graph Theory Ramsey Theory
Progress
In other words, is $G$ Ramsey size linear?See also the entry in the graphs problem collection.
Source: erdosproblems.com/568 | Last verified: January 15, 2026