Arrangeability and Clique Subdivisions

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 v1, v2,..., vn in such a way that for every integer i with 1 ≤ i ≤ n, at most k vertices among {v1, v2,..., vi} have a neighbor v ∈ {vi+1, vi+2,..., vn} that is adjacent to vi. We prove that for every integer p ≥ 1, if a graph G is not p 8-arrangeable, then it contains a Kp-subdivision. By a result of Chen and Schelp this implies that graphs with no Kp-subdivision have “linearly bounded Ramsey numbers, ” and by a result of Kierstead and Trotter it implies that such graphs have bounded “game chromatic number.