The game chromatic number of trees and forests - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Article Dans Une Revue Discrete Mathematics and Theoretical Computer Science Année : 2015

The game chromatic number of trees and forests

Résumé

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.
Fichier principal
Vignette du fichier
2027-9748-1-PB.pdf (393.74 Ko) Télécharger le fichier
Origine : Accord explicite pour ce dépôt
Loading...

Dates et versions

hal-01349045 , version 1 (26-07-2016)

Identifiants

Citer

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

Collections

TDS-MACS
78 Consultations
2054 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More