Planar Graph Coloring with an Uncooperative Partner
Planar Graph Coloring with an Uncooperative Partner
复制标题
DOI：
10.1090/dimacs/009/08
复制
发表时间：
1994-10
期刊：
影响因子：
--
通讯作者：
H. Kierstead;W. T. Trotter
中科院分区：
文献类型：
--
作者：
H. Kierstead;W. T. Trotter
证明了平面图的对策色数至多为33。更一般地，存在函数f：f\l --+ f\l，使得对于每个n E f\l。如果一个图不含Kn·的同胚，则它的对策色数至多为f（n）.特别地，一个图的对策色数是有界的。我们的证明的动机是由的概念，这是第一次介绍了由Guantao和Schelp在拉姆齐理论设置的p-pronunciation。John Wiley & Sons，Inc.
We show that the game chromatic number of a planar graph is at most 33. More generally, there exists a function f: f\l --+ f\l so that for each n E f\l. if a graph does not contain a homeomorph of Kn• then its game chromatic number is at most f(n). In particular, the game chromatic number of a graph is bounded in terms of its genus. Our proof is motivated by the concept of p-arrangeability, which was first introduced by Guantao and Schelp in a Ramsey theoretic setting. © 1994 John Wiley & Sons, Inc.