1993•Combinatorics Probability ComputingRequires access
Ramsey Size Linear Graphs
Paul L. Erdos, Ralph J. Faudree, Cecil Rousseau, RICHARD H. SCHELP
Open publisher page 7 citations
Abstract
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) ≤ Cn . It will be shown that any graph G with p vertices and q ≥ 2 p − 2 edges is not Ramsey size linear, and this bound is sharp. Also, if G is connected and q ≤ 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.