Playing a Game to Bound the Chromatic Number

AbstractWe provide here a new method for proving several known bounds on the chromatic number of a graph in a unified manner. To do so, we view vertices of a graph as players in a strategic game. Each player has the same set of actions, which is a set of colors. In a certain profile, where each vertex has chosen a color, a vertex gets a payoff equal to zero if its color is the same as one of its neighbors. Otherwise, the vertex gets as a payoff the number of vertices that chose the same color as its own color. In a pure Nash equilibrium of such a game, no vertex can improve its payoff by deviating unilaterally. We prove that, if we start with the trivial proper coloring, where each vertex chooses its unique name as a color, then any selfish improvement sequence (i.e., a sequence of steps, where at each step a single vertex changes its color in order to improve its payoff) reaches a pure Nash equilibrium in polynomial time, and that the number of colors used by any pure Nash equilibrium satisfies four know...