Game R-Proper Chromatic Numbers

Abstract

Consider the following two-person game on a graph $G$. The two players start with two color choices only, taking turns coloring any uncolored vertex with the restriction that any coloring must be a proper coloring. A third (or fourth, etc.) color can only be used when forced to maintain a proper coloring. One player, the minimizer, is trying to force the smallest number of colors possible. The other player, the maximizer, is trying to force the largest number of colors possible. This game proper chromatic number, denoted ${\chi }_{(E,g)}(G)$, is the minimum number of colors used when both players play optimally.

The advantage of the game proper chromatic number is that it is comparable to other published game chromatic variants, particularly the game chromatic number II and the game Grundy number.

This paper also considers extensions of the game proper chromatic number through generalized regions of the graph. Let $R=\{R_1,R_2,\dots ,R_t\}$ such that $\bigcup R_i=V(G)$. It is convenient to think of these $R_i$’s as regions of interest in graph $G$. In particular, extensions to closed neighborhoods and open neighborhoods maintaining the restriction that all colorings must be “proper” in the sense that no $R_i$ is monochromatic are considered for some natural classes of graphs.

The minimum number of colors necessary provided each player plays optimally, following the rules established for the game proper chromatic number, is denoted ${\chi }_{(N[v],g)}(G)$ and ${\chi }_{(N(v),g)}(G)$ for the game closed neighborhood proper chromatic number and the game open neighborhood chromatic number, respectively.