Multi-color √m graph Ramsey bound

Status open high confidence

The conjecture asks whether the two-color bound $r_2(G; 2) \leq 2^{c\sqrt{m}}$ for graphs $G$ with $m$ edges and no isolated vertices extends to $q \geq 3$ colors. The source paper itself resolves the analogous problem for $k$-uniform hypergraphs with $k \geq 3$, proving an upper bound of $\mathrm{tw}_k(O(\sqrt{m}))$ for all $q \geq 2$, but the argument is specific to $k \geq 3$ and does not apply to graphs ($k=2$). No follow-up paper resolving or substantially advancing this specific $k=2$, $q \geq 3$ problem was found in the literature.

Reviewer notes. No follow-up resolving the k=2 multicolor case was found. The paper arXiv:2312.13965 (Bradač, Fox, Sudakov, 2024, Research in the Mathematical Sciences) addresses the growth rate of multicolor Ramsey numbers of 3-uniform hypergraphs but is a different question. The arXiv:2410.17197 improvement on multicolor Ramsey numbers concerns diagonal Ramsey numbers R_r(k) for complete graphs, not the general-graph sqrt(m) bound. The open problem remains: prove or disprove r_2(G; q) \leq 2^{c_q \sqrt{m}} for q \geq 3.

Auto-reviewed 2026-05-15 with claude-sonnet-4-6 (web search enabled).