Problem Statement
Let $\epsilon >0$. Is it true that, if $k$ is sufficiently large, then\[R(G)>(1-\epsilon)^kR(k)\]for every graph $G$ with chromatic number $\chi(G)=k$?
Even stronger, is there some $c>0$ such that, for all large $k$, $R(G)>cR(k)$ for every graph $G$ with chromatic number $\chi(G)=k$?
Even stronger, is there some $c>0$ such that, for all large $k$, $R(G)>cR(k)$ for every graph $G$ with chromatic number $\chi(G)=k$?
Categories:
Graph Theory Ramsey Theory
Progress
Erdős originally conjectured that $R(G)\geq R(k)$, which is trivial for $k=3$, but fails already for $k=4$, as Faudree and McKay [FaMc93] showed that $R(W)=17$ for the pentagonal wheel $W$.Since $R(k)\leq 4^k$ this is trivial for $\epsilon\geq 3/4$. Yuval Wigderson points out that $R(G)\gg 2^{k/2}$ for any $G$ with chromatic number $k$ (via a random colouring), which asymptotically matches the best-known lower bounds for $R(k)$.
This problem is #12 and #13 in Ramsey Theory in the graphs problem collection.
Source: erdosproblems.com/87 | Last verified: January 13, 2026