The eternal game chromatic number of a graph

Abstract

Game coloring is a two-player game in which each player properly colors one vertex of a graph at a time until all the vertices are colored. An “eternal” version of game coloring is introduced in this paper in which the vertices are colored and re-colored from over a sequence of rounds. In a given round, each vertex is colored, or re-colored, once, so that a proper coloring is maintained. Player 1 wants to maintain a proper coloring forever, while player 2 wants to force the coloring process to fail. The eternal game chromatic number of a graph $G$ is defined to be the minimum number of colors needed in the color set so that player 1 can always win the game on $G$. The goal of this paper is to introduce this problem, consider several variations of this game, show its behavior on some elementary classes of graphs, and make some conjectures.