\(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.