Skip to Main content Skip to Navigation
Journal articles

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.
Document type :
Journal articles
Complete list of metadata

Cited literature [17 references]  Display  Hide  Download

https://hal.inria.fr/hal-01349045
Contributor : Coordination Episciences Iam Connect in order to contact the contributor
Submitted on : Tuesday, July 26, 2016 - 5:46:08 PM
Last modification on : Saturday, February 27, 2021 - 3:52:02 PM

File

2027-9748-1-PB.pdf
Explicit agreement for this submission

Identifiers

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. ⟨10.46298/dmtcs.2130⟩. ⟨hal-01349045⟩

Share

Metrics

Record views

62

Files downloads

1690