Zentralblatt MATH
Publications of (and about) Paul Erdös
Zbl.No: 273.05111
Autor: Burr, Stefan A.; Erdös, Paul; Spencer, J.H.
Title: Ramsey theorems for multiple copies of graphs. (In English)
Source: Trans. Am. Math. Soc. 209, 87-99 (1975).
Review: If G and H are graphs, define the ``Ramsey number'' r(G,H) to be the least number p such that if the edges of the complete graph Kp are colored red and blue (say), either the red graph contains G as a subgraph or the blue graph contains H. Let mG denote the union of m disjoint copies of G. The following result is proved: Let G and H have k and l points respectively and have point independence numbers of i and j respectively. Then N-1 \leq r(mG,nH) \leq N+C, where N = km+ln- max (mi,nj) and where C is an effectively computable function of G and H. The method used permits exact evaluation of r(mG,nH) for various choices of G and H, especially when m = n or G = H. In particular, r(mK3,nK3) = 3m+2n when m \geq n, m \geq 2.
Classif.: * 05C35 Extremal problems (graph theory)
05C15 Chromatic theory of graphs and maps
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag