OPENHARDgraph theoryRamsey theory
Let $\epsilon >0$. Is it true that if $k$ is sufficiently large, then $R(G)>(1-\epsilon)^kR(k)$ for every graph $G$ with $\chi(G)=k$?
Notes: Erdos's original conjecture R(G) >= R(k) fails for k=4 (pentagonal wheel). Wigderson showed R(G) >> 2^{k/2} for any graph with chromatic number k.
AI Status: NONE · 0 total attempts