The game chromatic number of trees and forests

2014/10/20 by Dunn, Charles, Larsen, Victor, Lindke, Kira +2
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1410.5223

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

Related

• The game chromatic index of trees of maximum degree 4 with at most three degree-four vertices in a row
• Edge colouring Game on Trees with maximum degree Δ=4
• The Game Chromatic Number of Complete Multipartite Graphs with No Singletons
• The game chromatic number of dense random graphs
• The game chromatic number of random graphs