Generalizing the coloring game from caterpillars to trees
Miguel A.D.R. Palma, Ana Furtado, Simone Dantas, Celina M.H. de Figueiredo · 2024
The coloring game is a two-player non-cooperative game conceived in 1981. Alice and Bob alternate turns to properly color the vertices of a finite graph G with t colors. Alice’s goal is to properly color the vertices of G with t colors; Bob’s aim is to prevent it. If, at any point, there is an uncolored vertex without an available color, Bob wins; otherwise, Alice wins. The game chromatic number χg(G) is the smallest t for Alice to have a winning strategy. In 1991, Bodlaender showed that a caterpillar was the smallest tree T with χg(T) = 4; in 1993, Faigle et al. proved χg(T) ≤ 4 for every tree T. In 2015, Dunn et al. proposed the characterization of forests with game chromatic numbers 3 and 4. In this paper, we extend results from caterpillars to more general trees, and establish sufficient conditions to ensure that a tree has game chromatic number 4.