PROVED
This has been solved in the affirmative.
Let $G$ be a graph with no isolated vertices and $m$ edges. Is it true that\[R(G) \leq 2^{O(m^{1/2})}?\]
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.
View the LaTeX source
This page was last edited 18 November 2025.
Additional thanks to: Zach Hunter and Desmond Weisenberg
When referring to this problem, please use the original sources of Erdős. If you wish to acknowledge this website, the recommended citation format is:
T. F. Bloom, Erdős Problem #546, https://www.erdosproblems.com/546, accessed 2026-01-16
