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