The game Grundy number of graphs - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Article Dans Une Revue Journal of Combinatorial Optimization Année : 2013

The game Grundy number of graphs

Résumé

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.
Fichier principal
Vignette du fichier
gameGrundy.pdf (187.7 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-00821597 , version 1 (23-10-2016)

Identifiants

Citer

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

Altmetric

Partager

Gmail Facebook X LinkedIn More