Conflict-free coloring games

Abstract

In 2003, the frequency assignment problem in a cellular network motivated Even et al. to introduce a new coloring problem: Conflict-Free coloring. Inspired by this problem and by the Gardner-Bodlaender’s coloring game, in 2020, Chimelli and Dantas introduced the Conflict-Free Closed Neighborhood \(k\)-coloring game (CFCN \(k\)-coloring game). The game starts with an uncolored graph \(G\), \(k\geq 2\) different colors, and two players, Alice and Bob, who alternately color the vertices of \(G\). Both players can start the game and respect the following legal coloring rule: for every vertex \(v\), if the closed neighborhood \(N[v]\) of \(v\) is fully colored then there exists a color that was used only once in \(N[v]\). Alice wins if she ends up with a Conflict-Free Closed Neighborhood \(k\)-coloring of \(G\), otherwise, Bob wins if he prevents it from happening. In this paper, we introduce the game for open neighborhoods, the Conflict-Free Open Neighborhood \(k\)-coloring game (CFON \(k\)-coloring game), and study both games on graph classes determining the least number of colors needed for Alice to win the game.