Bounds for the game coloring number of planar graphs with a specific girth

Abstract

Let $\mathrm{co}{\mathrm{l}}_{\mathrm{g}}(G)$ be the game coloring number of a given graph $G.$ Define the game coloring number of a family of graphs $\mathcal{H}$ as $\mathrm{co}{\mathrm{l}}_{\mathrm{g}}(\mathcal{H}):=\max \{\mathrm{co}{\mathrm{l}}_{\mathrm{g}}(G):G\in \mathcal{H}\}.$ Let ${\mathcal{P}}_k$ be the family of planar graphs of girth at least $k.$ We show that $\mathrm{co}{\mathrm{l}}_{\mathrm{g}}({\mathcal{P}}_7)\le 5.$ This result extends a result about the coloring number by Wang and Zhang {WZ11} ($\mathrm{co}{\mathrm{l}}_{\mathrm{g}}({\mathcal{P}}_8)\le 5).$ We also show that these bounds are sharp by constructing a graph $G$ where $G\in \mathrm{co}{\mathrm{l}}_{\mathrm{g}}({\mathcal{P}}_k)\ge 5$ for each $k\le 8$ such that $\mathrm{co}{\mathrm{l}}_{\mathrm{g}}(G)=5.$ As a consequence, $\mathrm{co}{\mathrm{l}}_{\mathrm{g}}({\mathcal{P}}_k)=5$ for $k=7,8.$