HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Reports

The game Grundy number of graphs

Frédéric Havet 1 Xuding Zhu 2
1 MASCOTTE - Algorithms, simulation, combinatorics and optimization for telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
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.
Document type :
Reports
Complete list of metadata

Cited literature [20 references]  Display  Hide  Download

https://hal.inria.fr/inria-00600738
Contributor : Frederic Havet Connect in order to contact the contributor
Submitted on : Wednesday, June 15, 2011 - 9:53:32 PM
Last modification on : Friday, February 4, 2022 - 3:18:56 AM
Long-term archiving on: : Friday, November 9, 2012 - 3:12:11 PM

File

RR-7646.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00600738, version 1

Citation

Frédéric Havet, Xuding Zhu. The game Grundy number of graphs. [Research Report] RR-7646, INRIA. 2011. ⟨inria-00600738⟩

Share

Metrics

Record views

199

Files downloads

581