Skip to Main content Skip to Navigation
Journal articles

The game Grundy number of graphs

Frédéric Havet 1 Xuding Zhu 2
1 COATI - Combinatorics, Optimization and Algorithms for Telecommunications
Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués, CRISAM - Inria Sophia Antipolis - Méditerranée
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 minimize the total number of colours used in the game, and Bob's goal is to maximize 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.
Complete list of metadatas

Cited literature [21 references]  Display  Hide  Download

https://hal.inria.fr/hal-00821597
Contributor : Frederic Havet <>
Submitted on : Sunday, October 23, 2016 - 4:11:54 PM
Last modification on : Thursday, March 5, 2020 - 12:20:45 PM

File

gameGrundy.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Frédéric Havet, Xuding Zhu. The game Grundy number of graphs. Journal of Combinatorial Optimization, Springer Verlag, 2013, 25 (4), pp.752-765. ⟨10.1007/s10878-012-9513-8⟩. ⟨hal-00821597⟩

Share

Metrics

Record views

332

Files downloads

280