Impartial coloring games

被引：5

作者：

Beaulieu, G. ^{[1
]}

Burke, K. ^{[2
]}

Duchene, E. ^{[3
]}

机构：

[1] Univ Sherbrooke, Sherbrooke, PQ J1K 2R1, Canada

[2] Wittenberg Univ, Springfield, OH 45503 USA

[3] Univ Lyon 1, LIRIS Lab, F-69622 Villeurbanne, France

来源：

THEORETICAL COMPUTER SCIENCE | 2013年 / 485卷

关键词：

Combinatorial games; Sprague-Grundy function; Graph coloring; KAYLES;

D O I：

10.1016/j.tcs.2013.02.032

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

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. (C) 2013 Elsevier B.V. All rights reserved.

引用

页码：49 / 60

页数：12

共 18 条

[1] The map-coloring game [J].