Exact Ramsey value for some trees
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)\).
Many Ramsey numbers have been determined for special families of graphs, including various combinations of paths, trees, stars and cycles. However, the following problem on Ramsey numbers for trees is still open.
Suppose that a tree \( T\) has a \( 2\)-coloring with \( k\) vertices in one color and \( l\) vertices in the other. It was proved in [1] that
Problem [1]
Is \(r(T) = 4k \) for every tree which is a bipartite graph with \(k\) vertices in one color and \(2k\) vertices in the other?