PLANAR GRAPH-COLORING WITH AN UNCOOPERATIVE PARTNER

被引：94

作者：

KIERSTEAD, HA ^{[1
]}

TROTTER, WT ^{[1
]}

机构：

[1] BELL COMMUN RES INC,MORRISTOWN,NJ

来源：

JOURNAL OF GRAPH THEORY | 1994年 / 18卷 / 06期

关键词：

D O I：

10.1002/jgt.3190180605

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

We show that the game chromatic number of a planar graph is at most 33. More generally, there exists a function f: N --> N so that for each n is-an-element-of N, if a graph does not contain a homeomorph of K(n), 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. (C) 1994 John Wiley & Sons, Inc.

引用

页码：569 / 584

页数：16