Zentralblatt MATH
Publications of (and about) Paul Erdös
Zbl.No: 248.05127
Autor: Bondy, J.A.; Erdös, Paul
Title: Ramsey numbers for cycles in graphs. (In English)
Source: J. Comb. Theory, Ser. B 14, 46-54 (1973).
Review: For two graphs G1 and G2, the Ramsey number R(G1,G2) is the minimum p such that for any graph G of order p, either G1 is a subgraph of G of G2 is a subgraph of the complement \bar G of G. The authors determine the Ramsey numbers in the cases where G1 and G2 are certain cycles. [These Ramsey numbers have since been established completely by J. Faudree and R. H. Schelp [Discrete Math. 8, 313-329 (1974; Zbl 294.05122)] and V. Rosta [J. Comb. Theory, Ser. B 15, 94-104, 105-120 (1973; Zbl 261.05118 and Zbl 261.05119)]. The authors show that R(Cn,Kr) \leq nr2 for all r and n and that (R(Cn,Kr) = (r-1)(n-1)+1 if n \geq r2-2. Let Kt+1r denote the complete (t+1)-partite graph K(r1, ... ,rt+1) for which ri = r for each i. Then R(Cn,Kt+1r) = t(n-1)+r for sufficiently large n.
Reviewer: G.Chartrand
Classif.: * 05C35 Extremal problems (graph theory)
05C15 Chromatic theory of graphs and maps
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag