##
**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 G_{1} and G_{2}, the Ramsey number R(G_{1},G_{2}) is the minimum p such that for any graph G of order p, either G_{1} is a subgraph of G of G_{2} is a subgraph of the complement \bar G of G. The authors determine the Ramsey numbers in the cases where G_{1} and G_{2} 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(C_{n},K_{r}) \leq nr^{2} for all r and n and that (R(C_{n},K_{r}) = (r-1)(n-1)+1 if n \geq r^{2}-2. Let K^{t+1}_{r} denote the complete (t+1)-partite graph K(r_{1}, ... ,r_{t+1}) for which r_{i} = r for each i. Then R(C_{n},K^{t+1}_{r}) = 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