Lower bounds for the game colouring number of partial \(k\)-trees and planar graphs (Q2427530)

The authors study some properties of the game coloring number of partial k-trees and planar graphs. The paper is structured in 4 sections. In the first section (introduction) some definitions and some notations used throughout the paper are presented. The game coloring number of a graph \(G\), denoted \(\text{col}_{g}(G)\) is introduced. In the second section the fact that the parameter of the game coloring number is monotonic is proven (theorem 1), i.e., if \(H\) is a subgraph of \(G\), then \(\text{col}_{g}(H) \leq \text{col}_{g}(G)\). In the third section it is proven that \(\text{col}_{g}(F_{k})= \text{col}_{g}(PF_{k})\), where \(F_{k}\) is the set of \(k\)-trees and \(PF_{k}\) is the set of partial \(k\)-trees (lemma 1). In theorem 2 it is proven that \(\text{col}_{g}(G) \leq 3k+2\), where \(G\) is a partial \(k\)-tree. In theorem 3 it is proven that there is for \(k \geq 2\) a partial \(k\)-tree \(G\) so that \(\text{col}_{g}(G) = 3k+2\). Corollary 1 of the theorems 2 and 3 is one of the main results of the paper: \(\text{col}_{g}(PF_{k}) = 3k+2\), for any integer \(k \geq 2\). In the last section theorem 4 is introduced and proved. There is a planar graph \(G\) with \(\text{col}_{g}(G) = 3k+2\).