Graphs with Linearly Bounded Ramsey Numbers

✍ Scribed by G.T. Chen; R.H. Schelp

• Publisher: Elsevier Science
• Year: 1993
• Tongue: English
• Weight: 439 KB
• Volume: 57
• Category: Article
• ISSN: 0095-8956
• DOI: 10.1006/jctb.1993.1012

✦ Synopsis

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