\(r(G)\) is bounded by \(r(\chi(G))\) (1)
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.
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.
|