Zentralblatt MATH
Publications of (and about) Paul Erdös
Zbl.No: 329.05116
Autor: Erdös, Paul; Faudree, Ralph J.; Rousseau, C.C.; Schelp, R.H.
Title: Generalized Ramsey theory for multiple colors. (In English)
Source: J. Comb. Theory, Ser. B 20, 250-264 (1976).
Review: From the authors' abstract: In this paper, we study the generalized Ramsey number r(G1, ... ,Gk) where the graphs G1, ... ,Gk consist of complete graphs, complete bipartite graphs, paths, and cycles. Our main theorem gives the Ramsey number for the case where G2, ... ,Gk are fixed and G1 \cong Cn or Pn with n sufficiently large. If among G2, ... ,Gk there are both complete graphs and odd cycles, the main theorem requires an additional hypothesis concerning the size of the odd cycles relative to their number. If among G2, ... ,Gk there are odd cycles but no complete graphs, then no additional hypothesis is necessary and complete results can be expressed in terms of a new type of Ramsey number which is introduced in this paper. For k = 3 and k = 4 we determine all necessary values of the new Ramsey number and so obtain, in particular, explicit and complete results for the cycle Ramsey numbers r(Cn,Cl,Ck) and r(Cn,Cl,Ck,Cm) when n is large.
Reviewer: J.E.Graver
Classif.: * 05C35 Extremal problems (graph theory)
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag