Exact Ramsey value for some trees

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

\(\displaystyle r(T) \geq \max \{2k+l-1,2l-1\}. \)

This leads to the following problem:

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?

1 P. Erdös, R. Faudree, C. C. Rousseau and R. H. Schelp, Ramsey numbers for brooms, Proceedings of the thirteenth Southeastern conference on combinatorics, graph theory and computing (Boca Raton, Fla., 1982), Congr. Numer. 35 (1982), 283-293.