Arrangeability and Clique Subdivisions

Summary Let k be an integer. A graph G is k-arrangeable (concept introduced by Chen and Schelp) if the vertices of G can be numbered v 1, v 2, …, v n in such a way that for every integer i with 1 ≤ i ≤ n, at most k vertices among {v 1, v 2, …, v i } have a neighbor $$v \in \{ v_{i+1},v_{i+2},\ldots,v_{n}\}$$ that is adjacent to v i . We prove that for every integer p ≥ 1, if a graph G is not 2500(p + 1)8-arrangeable, then it contains a K p -subdivision. By a result of Chen and Schelp this implies that graphs with no K p -subdivision have “linearly bounded Ramsey numbers,” and by a result of Kierstead and Trotter it implies that such graphs have bounded “game chromatic number.”