The game chromatic number of trees and forests

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 w...

Full description

Saved in:
Bibliographic Details
Published in:Discrete mathematics and theoretical computer science 2015-08, Vol.17 no.2 (Graph Theory), p.31-48
Main Authors: Dunn, Charles, Larsen, Victor, Lindke, Kira, Retter, Troy, Toci, Dustin
Format: Article
Language:English
Subjects:
[info.info-dm] computer science [cs]/discrete mathematics [cs.dm]
Computer Science
Discrete Mathematics
forest
Forests
game chromatic number
Mathematics
tree
Trees
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:1365-8050
1462-7264
1365-8050
DOI:10.46298/dmtcs.2130