Planar graph coloring with an uncooperative partner
Authors:
- H. A. KiersteadHKH. A. Kierstead
- 1 October 1994
- journal article
- research article
- Published by Wiley in Journal of Graph Theory
- Vol. 18 (6) , 569-584
Abstract
We show that the game chromatic number of a planar graph is at most 33. More generally, there exists a function f: ℕ → ℕ so that for each n ∈ ℕ, 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.Keywords
This publication has 3 references indexed in Scilit:
- On the complexity of some coloring games1991
- The Ramsey number of a graph with bounded maximum degreeJournal of Combinatorial Theory, Series B, 1983
- On sets of integers containing k elements in arithmetic progressionActa Arithmetica, 1975