Graphs with Linearly Bounded Ramsey Numbers

A graph G of order n is p-arrangeable if its vertices can be ordered as v1, v2, ...,vn such that |NLi (NRi (vi))| ≤ p for each 1 ≤ i ≤ n − 1, where Li = {v1, v2, ..., vi}, Ri = {vi+1, vi+2, ..., vn}, and NA(B) denotes the neighbors of B which lie in A. We prove that for each p ≥ 1, there is a constant c (depending only on p) such that the Ramsey number r(G, G) ≤ cn for each p-arrangeable graph G of order n. Further we prove that there exists a fixed positive integer p such that all planar graphs are p-arrangeable.