Kayles and Nimbers

✍ Scribed by Hans L. Bodlaender; Dieter Kratsch

• Book ID: 102574620
• Publisher: Elsevier Science
• Year: 2002
• Tongue: English
• Weight: 118 KB
• Volume: 43
• Category: Article
• ISSN: 0196-6774
• DOI: 10.1006/jagm.2002.1215

✦ Synopsis

Kayles is a combinatorial game on graphs. Two players select alternatingly a vertex from a given graph G-a chosen vertex may not be adjacent or equal to an already chosen vertex. The last player that can select a vertex wins the game. The problem to determine which player has a winning strategy is known to be PSPACEcomplete. Because of certain characteristics of the Kayles game, it can be analyzed with Sprague-Grundy theory. In this way, we can show that the problem is polynomial time solvable on graphs with a bounded asteroidal number. It is shown that the problem can be solved in O n 3 time on cocomparability graphs and circular arc graphs, and in O n 1+1/ log 3 = O n 1 631 time on cographs.  2002 Elsevier Science (USA)