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

dmtcs:2130 - Discrete Mathematics & Theoretical Computer Science, August 17, 2015, Vol. 17 no.2 - https://doi.org/10.46298/dmtcs.2130
The game chromatic number of trees and forestsArticle

Authors: Charles Dunn ORCID1; Victor Larsen 2; Kira Lindke 3; Troy Retter 4; Dustin Toci 5

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.


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]
Funding:
    Source : OpenAIRE Graph
  • REU Site: Willamette Valley Consortium for Undergraduate Mathematics Research; Funder: National Science Foundation; Code: 0649068

Consultation statistics

This page has been seen 472 times.
This article's PDF has been downloaded 1631 times.