On trees with game chromatic number 4

Abstract

The coloring game is a two-player non-cooperative game conceived by Steven Brams, first published in 1981. In this game, 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)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\chi _g(G)$$\end{document} of a graph G is the smallest t for Alice to have a winning strategy. While the game chromatic number of trees is known to be at most four (Faigle et al. 1993), the characterization of trees with game chromatic numbers 3 and 4 remains an open problem (Dunn et al. 2015). In this paper, we extend results on caterpillars to more general trees, and establish sufficient conditions for a tree to have game chromatic number 4. The techniques developed contribute to the construction of infinite families of trees with game chromatic number 4, and clarify the relation between local configurations and global coloring strategies.