Problem Statement
We say $G$ is Ramsey size linear if $R(G,H)\ll m$ for all graphs $H$ with $m$ edges and no isolated vertices.
Are there infinitely many graphs $G$ which are not Ramsey size linear but such that all of its subgraphs are?
Are there infinitely many graphs $G$ which are not Ramsey size linear but such that all of its subgraphs are?
Categories:
Graph Theory Ramsey Theory
Progress
Asked by Erdős, Faudree, Rousseau, and Schelp [EFRS93]. $K_4$ is the only known example of such a graph.Wigderson [Wi24] has proved that there are infinitely many such graphs (although his proof is not explicit, and an explicit example of such a graph apart from $K_4$ is still unknown).
Source: erdosproblems.com/79 | Last verified: January 13, 2026