# $$r(G)$$ is bounded by $$r(\chi(G))$$ (1)

For two graphs $$G$$ and $$H$$, let $$r(G,H)$$ denote the smallest integer $$m$$ satisfying the property that if the edges of the complete graph $$K_m$$ are colored in red and blue, then there is either a subgraph isomorphic to $$G$$ with all red edges or a subgraph isomorphic to $$H$$ with all blue edges. The classical Ramsey numbers are those for the complete graphs and are denoted by $$r(s,t)= r(K_s, K_t)$$. If $$s=t$$, we write $$r(s)=r(s, s)$$.

For a graph $$G$$, the chromatic number $$\chi(G)$$ is the least integer $$k$$ such that the vertices of $$G$$ can be colored in $$k$$ colors so that adjacent vertices have different colors. If $$\chi(G) \leq k$$, we say that $$G$$ is $$k$$-colorable. The following problem relates Ramsey numbers to chromatic numbers.

# A problem on $$k$$-chromatic graphs [1]

Let $$G$$ denote a graph on $$n$$ vertices with chromatic number $$k$$. Is it true that $r(G) > (1-\epsilon)^k r(k)$ holds for any fixed $$\epsilon$$, $$0 < \epsilon < 1$$, provided $$n$$ is large enough?

Bibliography
1 P. Erdös, Some of my favourite problems in number theory, combinatorics, and geometry, Combinatorics Week (Portuguese) (São Paulo, 1994), Resenhas 2 (1995), 165-186.