The Harmonious Coloring Game

A harmonious k-coloring of a graph G is a 2-distance proper k-coloring of its vertices such that each edge is uniquely identified by the colors of its endpoints. Here, we introduce its game version: the harmonious coloring game. In this two-player game, Alice and Bob alternately select an uncolored vertex and assigns to it a color in {1, . . . , k} with the constraint that, at every turn, the set of colored vertices induces a valid partial harmonious coloring. Alice wins if all vertices are colored; otherwise, Bob wins. The harmonious game chromatic number χ hg (G) is the minimum integer k such that Alice has a winning strategy with k colors. In this paper, we prove the PSPACE-hardness of three variants of this game. As a by-product, we prove that a variant introduced by Chen et al. in 1997 of the classical graph coloring game is PSPACE-hard. We also obtain lower and upper bounds for χ hg (G) in graph classes, such as paths, cycles, grids and forests of stars.