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

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