Authors: Charles Dunn 1; Victor Larsen 2; Kira Lindke 3; Troy Retter 4; Dustin Toci 5
0000-0002-0526-9012##NULL##NULL##NULL##NULL
Charles Dunn;Victor Larsen;Kira Lindke;Troy Retter;Dustin Toci
1 Linfield College
2 Kennesaw State University
3 Michigan Technological University
4 Emory University [Atlanta, GA]
5 Auteur indépendant
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.