##
**Zentralblatt MATH**

**Publications of (and about) Paul Erdös**

**Zbl.No: ** 794.05085

**Autor: ** Erdös, Paul; Faudree, Ralph J.; Rousseau, C.C.; Schelp, R.H.

**Title: ** Ramsey size linear graphs. (In English)

**Source: ** Comb. Probab. Comput. 2, No.4, 389-399 (1993).

**Review: ** A graph G is Ramsey size linear if there is a constant C such that for any graph H with n edges and no isolated vertices, the Ramsey number r(G,H) \leq Cn. It will be shown that any graph G with p vertices and q \geq 2p-2 edges is not Ramsey size linear, and this bound is sharp. Also, if G is connected and q \leq p+1, then G is Ramsey size linear, and this bound is sharp also. Special classes of graphs will be shown to be Ramsey size linear, and bounds on the Ramsey numbers will be determined.

**Classif.: ** * 05C55 Generalized Ramsey theory

05C35 Extremal problems (graph theory)

**Keywords: ** Ramsey size linear graphs; Ramsey number

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag