Impartial coloring games

• Introduction of a new set of games derived from graph coloring problems.
• Study of the game complexity in the general case. PSPACE-hardness is proved for almost each variant.
• Outcomes (P/N positions) and Grundy values are examined for paths and cycles. Polynomial computations.
• Opens the door to other families of games build from graph optimization problems (e.g. domination problem).

Coloring games are combinatorial games where the players alternate painting uncolored vertices of a graph one of k>0 colors. Each different ruleset specifies that game’s coloring constraints. This paper investigates six impartial rulesets (five new), derived from previously-studied graph coloring schemes, including proper map coloring, oriented coloring, 2-distance coloring, weak coloring, and sequential coloring. For each, we study the outcome classes for special cases and general computational complexity. In some cases we pay special attention to the Grundy function.