Arrangeability and Clique Subdivisions
Arrangeability and Clique Subdivisions
复制标题
可安排性和集团细分
DOI：
--
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
R. Thomas
中科院分区：
文献类型：
--
作者：
V. Rödl;R. Thomas
令k为整数。图 G 是 k 可排列的（Chen 和 Schhelp 引入的概念），如果 G 的顶点可以编号为 v 1, v 2, …, v n ，使得对于 1 ≤ i ≤ n 的每个整数 i，{v 1, v 2, …, v i } 中最多 k 个顶点有一个邻居 (v in { v_{i+1},v_{i+2},ldots,v_{n}}) 与 v i 相邻。我们证明，对于每个整数 p ≥ 1，如果图 G 不是 2500(p + 1)8 可排列的，那么它包含一个 K p 细分。根据 Chen 和 Schhelp 的结果，这意味着没有 K p 细分的图具有“线性有界拉姆齐数”，而根据 Kierstead 和 Trotter 的结果，这意味着此类图具有有界“游戏色数”。
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.”