Impartial coloring games

详细信息    查看全文

• 作者：G. Beaulieu^a ; ^{gabriel.beaulieu@usherbrooke.ca} ; K. Burke^b ; ^{kburke@wittenberg.edu} ; E. Duchê ; ne^c ; ^{eric.duchene@univ-lyon1.fr}
• 关键词：Combinatorial games ; Sprague&ndash ; Grundy function ; Graph coloring
• 刊名：Theoretical Computer Science
• 出版年：2013
• 出版时间：13 May, 2013
• 年：2013
• 卷：485
• 期：Complete
• 页码：49-60
• 全文大小：821 K

文摘

Coloring games are combinatorial games where the players alternate painting uncolored vertices of a graph one of 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.