The game chromatic number of trees and forests

Abstract : While the game chromatic number of a forest is known to be at most 4, no simple criteria are known for determining the game chromatic number of a forest. We first state necessary and sufficient conditions for forests with game chromatic number 2 and then investigate the differences between forests with game chromatic number 3 and 4. In doing so, we present a minimal example of a forest with game chromatic number 4, criteria for determining in polynomial time the game chromatic number of a forest without vertices of degree 3, and an example of a forest with maximum degree 3 and game chromatic number 4. This gives partial progress on the open question of the computational complexity of the game chromatic number of a forest.
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2015, Vol. 17 no.2 (2), pp.31-48
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01349045
Contributeur : Coordination Episciences Iam <>
Soumis le : mardi 26 juillet 2016 - 17:46:08
Dernière modification le : mercredi 6 septembre 2017 - 14:06:13

Fichier

2027-9748-1-PB.pdf
Accord explicite pour ce dépôt

Identifiants

  • HAL Id : hal-01349045, version 1

Collections

Citation

Charles Dunn, Victor Larsen, Kira Lindke, Troy Retter, Dustin Toci. The game chromatic number of trees and forests. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2015, Vol. 17 no.2 (2), pp.31-48. 〈hal-01349045〉

Partager

Métriques

Consultations de la notice

69

Téléchargements de fichiers

275