Upper bound on r(tree, complete multi-partite)

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

Chvátal [1] proved that

\(\displaystyle r(T,K_m) = (m-1)(n-1)+1 \)

for any tree on \( n\) vertices. This result was generalized to graphs with small chromatic number. For a graph \( G\) with chromatic number \( \chi(G)\), it was shown [3] that

\(\displaystyle r(T, G) = (\chi(G)-1)(n-1)+1\)

for any tree \( T\) on \( n\) vertices, provided \( n\) is sufficiently large.

Conjecture [2]

If \(m_1 \leq \ldots \leq m_k\), then \[ r(T,K_{m_1,\ldots,m_k}) \leq (\chi(G) -1) (r(T,K_{m_1,m_2})-1)+ m_1 \] where \(T\) is any tree on \(n\) vertices, and \(n\) is large enough.

Bibliography
1 V. Chvátal, Tree-complete graph Ramsey numbers, J. Graph Theory 1 (1977), 93.

2 P. Erdös, R. Faudree, C. C. Rousseau and R. H. Schelp, Multipartite graph-sparse graph Ramsey numbers, Combinatorica 5 (1985) no. 4, 311-318.

3 S. A. Burr, P. Erdös, R. J. Faudree, R. J. Gould, M. S. Jacobson, C. C. Rousseau and R. H. Schelp, Goodness of trees for generalized books, Graphs Combin. 3 (1987) no. 1, 1-6.