Coloring games on squares of graphs

AbstractThe game coloring number of the square of a graph G, denoted by gcol(G2), 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 rG, 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(G2)≤kΔ(G)+⌊(1+1a)rG⌋+rG+2. This implies that if G is a partial k-tree and a