Problem Statement
Let $G$ be a graph with no isolated vertices and $m$ edges. Is it true that\[R(G) \leq 2^{O(m^{1/2})}?\]
Categories:
Graph Theory Ramsey Theory
Progress
This is true, and was proved by Sudakov [Su11]. The analogous question for $\geq 3$ colours is still open.Alon, Krivelevich, and Sudakov [AKS03] had earlier given a short proof of this when $G$ is bipartite.
A more precise question is [545].
This problem is #11 in Ramsey Theory in the graphs problem collection.
Source: erdosproblems.com/546 | Last verified: January 15, 2026