The Eternal Game Chromatic Number of a Graph

zbMATH Open1466.05136arXiv1811.02332MaRDI QIDQ4995308

William F. Klostermeyer, Hannah Mendoza

Publication date: 23 June 2021

Abstract: Game coloring is a well-studied 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 a color set 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

. We consider several variations of this new game and show its behavior on some elementary classes of graphs.

Full work available at URL: https://arxiv.org/abs/1811.02332

zbMATH Keywords

game coloring

Mathematics Subject Classification ID

2-person games (91A05) Games involving graphs (91A43) Distance in graphs (05C12) Games on graphs (graph-theoretic aspects) (05C57)