The game chromatic number of trees and forests
Charles L Dunn, Victor Larsen, Kira Lindke, Troy Retter, Dustin Toci
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.
Full Text: PDF PostScript