The game coloring number of planar graphs with a specific girth
type: Item
instance of: scholarly article
title: The game coloring number of planar graphs with a specific girth
zbMATH Open document ID: 1390.05146
author: Keaitsuda Nakprasit
author: Kittikorn Nakprasit
published in: Graphs and Combinatorics
publication date: 2018-04-13T00:00:00Z
review text: The authors study the game coloring number \(\mathrm{col}_g(G)\) of a graph \(G\), introduced by \textit{X. Zhu} [Discrete Math. 215, No. 1--3, 245--262 (2000; Zbl 0947.05031)]. The game coloring number is defined via the following game, played on the vertices of \(G\) by two players, Alice and Bob. All vertices of \(G\) are initially unmarked. Alice and Bob alternate turns, starting with Alice, and on each turn, the active player chooses an unmarked vertex of \(G\) and marks it. Play continues until every vertex of \(G\) is marked. Letting \(b(v)\) denote the number of neighbors of \(v\) that are marked before \(v\) is marked, the goal of Alice is to minimize \(\max_v b(v)\), while the goal of Bob is to maximize \(\max_v b(v)\). When both players play optimally according to these goals, we define \(\mathrm{col}_g(G)\) as the resulting value of \(b(v)+1\). The game coloring number is an upper bound on the closely related game chromatic number \(\chi_g(G)\). The relation between these parameters appears to be analogous to the relation between the coloring number of a graph (i.e., its degeneracy plus \(1\)), and its ordinary chromatic number. For a class of graphs \(\mathcal{H}\), we define \(\mathrm{col}_g(\mathcal{H})\) to be \(\max\{\mathrm{col}_g(G) :\;G \in \mathcal{H}\}\). We define \(\mathcal{P}_k\) to be the class of planar graphs having girth at least \(k\), i.e., having no cycle of length less than \(k\). As discussed in the paper, several authors have obtained upper and lower bounds on \(\mathrm{col}_g(\mathcal{P}_k)\) for various values of \(k\). In this paper, the authors prove that \(\mathrm{col}_g(\mathcal{P}_7) \leq 5\), and construct a planar graph \(G\) of girth \(8\) satisfying \(\mathrm{col}_g(G) = 5\), thereby establishing \(\mathrm{col}_g(\mathcal{P}_7) = \mathrm{col}_g(\mathcal{P}_8) = 5\). This extends, in particular, a result of \textit{Y. Wang} and \textit{Q. Zhang} [ibid. 311, No. 10--11, 844--849 (2011; Zbl 1223.05047)] stating that \(\math…
reviewed by: Gregory J. Puleo
Mathematics Subject Classification ID: 05C57
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C10
Mathematics Subject Classification ID: 91A43
Mathematics Subject Classification ID: 91A05
zbMATH DE Number: 6859820
zbMATH Keywords: game coloring number
zbMATH Keywords: game chromatic number
zbMATH Keywords: planar graph
zbMATH Keywords: girth
MaRDI profile type: Publication
full work available at URL: s00373-018-1877-9
OpenAlex ID: W2790307852
cites work: ON THE COMPLEXITY OF SOME COLORING GAMES
cites work: Decompositions of quadrangle-free planar graphs
cites work: Q4201568
cites work: Game chromatic number of outerplanar graphs
cites work: Edge-partitions of planar graphs and their game coloring numbers
cites work: A simple competitive graph coloring algorithm
cites work: Very asymmetric marking games
cites work: The game coloring number of planar graphs with a given girth
cites work: Decomposing a planar graph with girth at least 8 into a forest and a matching
cites work: Lower bounds for the game colouring number of partial \(k\)-trees and planar graphs
cites work: The game coloring number of planar graphs
cites work: The game coloring number of pseudo partial \(k\)-trees
cites work: Refined activation strategy for the marking game
DOI: 10.1007/S00373-018-1877-9
Recommended article: The game coloring number of planar graphs with a given girth
Recommended article: Edge-partitions of planar graphs and their game coloring numbers
Recommended article: The coloring game on planar graphs with large girth, by a result on sparse cactuses
Recommended article: The game coloring number of planar graphs
Recommended article: Q3138289
Recommended article: A simple competitive graph coloring algorithm
Recommended article: A bound for the game chromatic number of graphs
Recommended article: A simple competitive graph coloring algorithm. III
Recommended article: Refined activation strategy for the marking game
Recommended article: Game chromatic number of outerplanar graphs
description: scientific article; zbMATH DE number 6859820