The game coloring number of planar graphs
type: Item
instance of: scholarly article
title: The game coloring number of planar graphs
zbMATH Open document ID: 0933.05052
author: Xuding Zhu
published in: Journal of Combinatorial Theory. Series B
publication date: 2000-04-04T00:00:00Z
review text: The game chromatic number of a graph \(G=(V, E)\) is the minimum number of colors, such that Alice has a winning strategy in the following game: turnwise, Alice and Bob color an uncolored vertex \(v\) of \(V\) with a color, different from colors already assigned to the neighbors of \(v\). Alice wins when \(G\) is colored; Bob wins when there are vertices to which no color can be assigned. In the coloring game, Alice and Bob turnwise color a vertex of \(G\). The outcome of the game is \(1+k\), where \(k\) is the maximum number of colored neighbors of a vertex when it is colored. Alice tries to minimize the outcome, while Bob tries to maximize it. The minimum outcome when Alice plays perfectly is the game coloring number, which is an upper bound for the game chromatic number. In this paper, it is shown that the game coloring number (and hence also the game chromatic number) of a planar graph is at most 19, improving upon an earlier bound of 30. This bound is obtained using the notion of light edges, a decomposition of the planar graph into subgraphs with special properties, and a detailed strategy for Alice. The paper also poses a number of central open questions in this area of research.
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C10
Mathematics Subject Classification ID: 91A43
zbMATH DE Number: 1346896
zbMATH Keywords: game chromatic number
zbMATH Keywords: coloring game
zbMATH Keywords: game coloring number
zbMATH Keywords: planar graph
reviewed by: Hans L. Bodlaender
MaRDI profile type: Publication
cites work: An acyclic analogue to Heawood's theorem
cites work: ON THE COMPLEXITY OF SOME COLORING GAMES
cites work: Generalization of a theorem of Kotzig and a prescribed coloring of the edges of planar graphs
cites work: On acyclic colorings of planar graphs
cites work: Structural Properties of Planar Maps with the Minimal Degree 5
cites work: On Light Edges and Triangles in Planar Graphs of Minimum Degree Five
cites work: A bound for the game chromatic number of graphs
cites work: Q4201568
cites work: Über eine von H. S. WILF angegebene Schranke für die chromatische Zahl endlicher Graphen
cites work: Game chromatic number of outerplanar graphs
cites work: Unterteilungen vollständiger Graphen in Graphen mit unendlicher chromatischer Zahl
cites work: Q4857375
cites work: Radius two trees specify χ‐bounded classes
cites work: Acyclic and oriented chromatic numbers of graphs
cites work: Q5344765
cites work: k-Degenerate Graphs
cites work: Decomposition of Finite Graphs Into Forests
cites work: Q4875686
description: scientific article; zbMATH DE number 1346896