Dunn, Charles and Larsen, Victor and Lindke, Kira and Retter, Troy and Toci, Dustin - The game chromatic number of trees and forests

dmtcs:2130 - Discrete Mathematics & Theoretical Computer Science, August 17, 2015, Vol. 17 no.2
The game chromatic number of trees and forests

Authors: Dunn, Charles and Larsen, Victor and Lindke, Kira and Retter, Troy and Toci, Dustin

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.


Source : oai:HAL:hal-01349045v1
Volume: Vol. 17 no.2
Section: Graph Theory
Published on: August 17, 2015
Submitted on: August 27, 2011
Keywords: game chromatic number,forest,tree,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]


Share

Browsing statistics

This page has been seen 20 times.
This article's PDF has been downloaded 71 times.