2012/02/26 by Gabriel Beaulieu, Beaulieu, Gabriel, Kyle Burke +4
Computer Science · Mathematics · Social Sciences · #Artificial Intelligence in Games #Combinatorics (math.CO) #Computational Complexity (cs.CC) #Digital Games and Media #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #cs.CC #cs.DM #math.CO
paper · pdf · doi:10.48550/arxiv.1202.5762
arxiv created 2012/02/26 · openalex publication_date 2012/02/26 · arxiv updated 2012/02/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.