Coloring games on squares of graphs

The game coloring number of the square of a graph G , denoted by gcol ( G 2 ) , was first studied by Esperet and Zhu. The ( a , b ) -game coloring number, denoted by ( a , b ) - gcol ( G ) , is defined like the game coloring number, except that on each turn Alice makes a moves and Bob makes b moves. For a graph G , the maximum average degree of G is defined as Mad ( G ) = max { 2 | E ( H ) | | V ( H ) | : H is a subgraph of G } . Let k be an integer. In this paper, by introducing a new parameter r G , which is defined through orientations and orderings of the vertices of G , we show that if a < Mad ( G ) / 2 ≤ k , then ( a , 1 ) - gcol ( G 2 ) ≤ k Δ ( G ) + ⌊ ( 1 + 1 a ) r G ⌋ + r G + 2 . This implies that if G is a partial k -tree and a < k , then ( a , 1 ) - gcol ( G 2 ) ≤ k Δ ( G ) + ( 1 + 1 a ) ( k 2 + 3 k + 2 2 ) + 2 ; if G is planar, then there exists a constant C such that gcol ( G 2 ) ≤ 5 Δ ( G ) + C . These improve previous corresponding known results. For a ≥ k ≥ Mad ( G ) and Δ ( G ) ≥ 2 k − 2 , we prove that ( a , 1 ) - gcol ( G 2 ) ≤ ( 3 k − 2 ) Δ ( G ) − k 2 + 4 k + 2 .