\(r(G)\) is bounded by \(r(\chi(G))\) (2)
Search
Subjects
 All (170)
 Ramsey Theory (40)
 Extremal Graph Theory (40)
 Coloring, Packing, and Covering (25)
 Random Graphs and Graph Enumeration (16)
 Hypergraphs (35)
 Infinite Graphs (14)
About Erdös
About This Site
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), 165186.

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), 2331.
