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 vertical bar E(H)vertical bar/vertical bar V(H)vertical bar : 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 Delta (G) + left perpendicular(1 + 1/ar(G)right perpendicular + r(G) + 2. This implies that if G is a partial k-tree and a < k, then (a, 1)-gcol(G(2)) <= k Delta (G) + (1 + 1/a) (k(2) + 3k + 2) + 2; if G is planar, then there exists a constant C such that gcol (G(2)) <= 5 Delta (G) + C. These improve previous corresponding known results. For a > k > Mad(G) and Delta (G) >= 2k - 2, we prove that (a, 1)-gcol (G(2)) <= (3k - 2)Delta (G) - k(2) + 4k + 2. (C) 2012 Elsevier B.V. All rights reserved.