The game coloring number of planar graphs with a specific girth (Q1743687): Difference between revisions

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 \(\mathrm{col}_g(\mathcal{P}_8) \leq 5\). The main tool used in the proof of the upper bound appears to be the activation strategy of \textit{H. A. Kierstead} [J. Comb. Theory, Ser. B 78, No. 1, 57--68 (2000; Zbl 1024.05029)], carried out on a carefully chosen linear ordering of the vertices of \(G\). The construction for the lower bound is a modification of a construction due to \textit{Y. Sekiguchi} [Discrete Math. 330, 11--16 (2014; Zbl 1295.05156)].