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 , 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.
Type de document :
Rapport
[Research Report] RR-7646, INRIA. 2011
Liste complète des métadonnées

Littérature citée [20 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00600738
Contributeur : Frederic Havet <>
Soumis le : mercredi 15 juin 2011 - 21:53:32
Dernière modification le : mercredi 31 janvier 2018 - 10:24:04
Document(s) archivé(s) le : vendredi 9 novembre 2012 - 15:12:11

Fichier

RR-7646.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • 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〉

Partager

Métriques

Consultations de la notice

317

Téléchargements de fichiers

362