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

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.

# Problem [1]

Prove that there is some $$\epsilon > 0$$ so that for all $$G$$ with chromatic number $$k$$, $\frac{r(G)}{r(k)} > \epsilon.$

This is a modified version of an old conjecture that $$r(G) \geq r(k)$$ which, however, has a counterexample for the case of $$n=4$$. It was given by Faudree and McKay [2] by showing $$r(W)= 17$$ for the pentagonal wheel $$W$$.

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.

2 R. Faudree and B. McKay, A conjecture of Erdös and the Ramsey number $$r(W_6)$$, J. Combinatorial Math. and Combinatorial Computing 13 (1993), 23-31.