The game Grundy number of graphs

The game Grundy number of graphs

0.00 Avg rating0 Votes
Article ID: iaor20132808
Volume: 25
Issue: 4
Start Page Number: 752
End Page Number: 765
Publication Date: May 2013
Journal: Journal of Combinatorial Optimization
Authors: ,
Keywords: combinatorial optimization, game theory
Abstract:

Given a graph G=(V,E), two players, Alice and Bob, alternate their turns in choosing uncoloured vertices to be coloured. Whenever an uncoloured vertex is chosen, it is coloured by the least positive integer not used by any of its coloured neighbours. Alice’s goal is to minimise the total number of colours used in the game, and Bob’s goal is to maximise it. The game Grundy number of G is the number of colours used in the game when both players use optimal strategies. It is proved in this paper that the maximum game Grundy number of forests is 3, and the game Grundy number of any partial 2‐tree is at most 7.

Reviews

Required fields are marked *. Your email address will not be published.