On the degree of trees with game chromatic number 4

¹ CEFET/RJ, Rio de Janeiro, Brazil
² IME, Fluminense Federal University, Rio de Janeiro, Brazil
³ COPPE, Federal University of Rio de Janeiro, Rio de Janeiro, Brazil

^* Corresponding author: mipalma@id.uff.br

Received: 21 December 2022
Accepted: 17 September 2023

Abstract

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.