Graphs with linearly bounded Ramsey numbers (Q2277497)

A graph G of order n is p-arrangeable if its vertices can be ordered as \(v_ 1,v_ 2,...v_ n\) such that \(| N_{L_ i}(N_{R_ i}(v_ i))| \leq p\) for each \(1\leq i\leq n-1\), where \(L_ i=\{v_ 1,v_ 2,...,v_ i\}\), \(R_ i=\{v_{i+1},v_{i+2},...,v_ n\}\), and \(N_ A(B)\) denotes the neighbors of B which lie in A. We prove that for each \(p\geq 1\), there is a constant c (depending only on p) such that the Ramsey number r(G,G)\(\leq 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.