Game Chromatic Number of Trees is 4

摘要

Consider the following two person game on a graph G. Players I and II move alternatingly with player I moving first. Each move consists of picking a node, say v, which is not yet colored and assigning one color from a prespecified set of colors to it in such a way that the resulting partial coloring of G is feasible, i.e. v must not get a color which has already been assigned to one of its neighbors in a previous move. The game is finished when either one of the players can not move any more. Player I wins, if all vertices of G are colored, otherwise player II wins. The game chromatic number of G is the smallest number of colors such that there is a winning strategy for player I. The authors answer an open problem from (Bod 90) by proving that every tree has game chromatic number = or