Zentralblatt MATH

Publications of (and about) Paul Erdös
Zbl.No:  792.05103
Autor:  Erdös, Paul; Faudree, Ralph J.; Rousseau, C.C.; Schelp, R.H.
Title:  Multipartite graph-tree Ramsey numbers. (In English)
Source:  Capobianco, Michael F. (ed.) et al., Graph theory and its applications: East and West. Proceedings of the first China-USA international conference, held in Jinan, China, June 9-20, 1986. New York: New York Academy of Sciences, Ann. N. Y. Acad. Sci. 576, 146-154 (1989).
Review:  Let T = Tn be a tree of order n, and F = K (m0,m1,...,mk) be the complete multipartite graph with parts of order m0 \leq m1 \leq ··· \leq mk. For n sufficiently large and m1 = m2 = 1, it has been shown that the Ramsey number r(F,T) = k(n-1)+1. This result is generalized by showing that with just m0 = 1 and n sufficiently large,

k(n-1)+1 \leq r(F,T) \leq k(r(K(1,m1),T)-1)+1.

Since it is known that r(K(1,m1),T) = n for the large class of trees that have no vertices of large degree, the upper and lower bounds are frequently identical. In all cases, these bounds are shown to differ by at most k.
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 Kp 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

r(F,G) \geq (\chi(F)-1) (n-1)+s(F).     (1)

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) Kn-1 \cup Ks(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(Kk,Tn) = (k-1)(n-1)+1 [J. Graph Theory 1, 93 (1977; Zbl 351.05120)], where Kk denotes the complete graph on k vertices and Tn denotes a tree on n vertices. The result of Chvátal has been generalized in many special cases by replacing the complete graph Kk by a graph F of chromatic number k, the tree Tn 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,Tn), when Tn is a large-order tree, and in particular to determine which large trees Tn are F-good. Since \chi(F) is important in determining the value of r(F,Tn), it is natural to carefully consider the case when F = K(m0,m1,...,mk) is a complete multipartite graph.
Not all trees are K(m0,m1,...,mk)-good when each mi \geq 2 or when m0 = 1 and mi \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

r(K(2,2), K(1,n-1)) > n+n ½-5n3/10

for n large. However, the principal result of [Graphs Comb. 3, 1-6 (1987; Zbl 612.05046)] is that each large-order tree TN is K(1,1,m2,m3,...,mk)-good. We will generalize this last result by proving the following theorem.
Theorem: If n is sufficiently large, then

r(K(1,m1, ...,mk),Tn) \geq max {k(n-1), k(r(K(1,m1), Tn)-2)}+1,

and

r(K(1,m1, ...,mk),Tn) \leq k{r(K(1,m1),TN)- 1}+1.


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

Books Problems Set Theory Combinatorics Extremal Probl/Ramsey Th.
Graph Theory Add.Number Theory Mult.Number Theory Analysis Geometry
Probabability Personalia About Paul Erdös Publication Year Home Page