On the degree of trees with game chromatic number 4

The coloring game is played by Alice and Bob on a finite graph G . They take turns properly coloring the vertices with t colors. The goal of Alice is to color the input graph with t colors, and Bob does his best to prevent it. If at any point there exists an uncolored vertex without available color, then Bob wins; otherwise Alice wins. The game chromatic number χ g ( G ) of G is the smallest number t such that Alice has a winning strategy. In 1991, Bodlaender showed the smallest tree T with χ g ( T ) equal to 4, and in 1993 Faigle et al. proved that every tree T satisfies the upper bound χ g ( T )≤4. The stars T = K 1, p with p ≥ 1 are the only trees satisfying χ g ( T ) = 2; and the paths T = P n , n ≥ 4, satisfy χ g ( T ) = 3. Despite the vast literature in this area, there does not exist a characterization of trees with χ g ( T ) = 3 or 4. We answer a question about the required degree to ensure χ g ( T ) = 4, by exhibiting infinitely many trees with maximum degree 3 and game chromatic number 4.