Since it is known that r(K(1,m_{1}),T) =

For simple graphs F and G, the Ramsey number r(F,G) is the smallest integer p such that if the edges of the complete graph K_{p} are colored red and blue, either the red subgraph contains a copy of F or the blue subgraph contains a copy of G. If F is a graph with chromatic number \chi(F), then the chromatic surplus s(F) is the smallest number of vertices in a color class under any \chi(F)-coloring of the vertices of F.

For any connected graph G of order n \geq s(F), the Ramsey number r(F,G) satisfies the inequality

This inequality follows from coloring red or blue the edges of a complete graph on (\chi(F)-1)(n-1)+s(F)-1 vertices such that the red subgraph is isomorphic to (\chi (F)-1) K_{n-1} \cup K_{s(F)-1} and the blue subgraph is isomorphic to the complement. When equality occurs in (1) we say that G is F-good. The concept of F-goodness generalizes the classical simple result of Chvátal that r(K_{k},T_{n}) = _{k} denotes the complete graph on k vertices and T_{n} denotes a tree on n vertices. The result of Chvátal has been generalized in many special cases by replacing the complete graph K_{k} by a graph F of chromatic number k, the tree T_{n} by a ``sparse'' graph G of order n, and the number 1 by s(F) (i.e., G is F-good). Even in the case when G is ``sparse'' but not F-good, the lower bound given in inequality (1) is in most cases a good approximation to the Ramsey number r(F,G).

Our purpose is to investigate the Ramsey number r(F,T_{n}), when T_{n} is a large-order tree, and in particular to determine which large trees T_{n} are F-good. Since \chi(F) is important in determining the value of r(F,T_{n}), it is natural to carefully consider the case when F = _{0},m_{1},...,m_{k})

Not all trees are K(m_{0},m_{1},...,m_{k})-good when each m_{i} \geq 2 or when m_{0} = _{i} \geq 2 for 1 \leq i \leq k. For example in [Ann. Discrete Math. 41, 79-89 (1989; Zbl 672.05063)] it was shown that

for n large. However, the principal result of [Graphs Comb. 3, 1-6 (1987; Zbl 612.05046)] is that each large-order tree T_{N} is K(1,1,m_{2},m_{3},...,m_{k})-good. We will generalize this last result by proving the following theorem.

Theorem: If n is sufficiently large, then

and

**Classif.: ** * 05C55 Generalized Ramsey theory

05C05 Trees
**Keywords: ** tree; multipartite graph; Ramsey number; chromatic number; chromatic surplus
**Citations: ** Zbl 351.05120; Zbl 672.05063; Zbl 612.05046

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag