Abstract | We give an efficient local search
algorithm that computes a good vertex coloring of a graph $G$. In
order to better illustrate this local search method, we view local
moves as selfish moves in a suitably defined game. In particular,
given a graph $G=(V,E)$ of $n$ vertices and $m$ edges, we define
the \emphgraph coloring game $\Gamma(G)$ as a strategic game
where the set of players is the set of vertices and the players
share the same action set, which is a set of $n$ colors. The
payoff that a vertex $v$ receives, given the actions chosen by all
vertices, equals the total number of vertices that have chosen the
same color as $v$, unless a neighbor of $v$ has also chosen the
same color, in which case the payoff of $v$ is 0. We show:
\beginitemize
\item The game $\Gamma(G)$ has always pure Nash equilibria. Each
pure equilibrium is a proper coloring of $G$. Furthermore, there
exists a pure equilibrium that corresponds to an optimum coloring.
\item We give a polynomial time algorithm $\mathcalA$ which
computes a pure Nash equilibrium of $\Gamma(G)$. \item The total
number, $k$, of colors used in \emphany pure Nash equilibrium
(and thus achieved by $\mathcalA$) is $k\leq\min\\Delta_2+1,
\fracn+ømega2, \frac1+\sqrt1+8m2, n-\alpha+1\$, where
$ømega, \alpha$ are the clique number and the independence number
of $G$ and $\Delta_2$ is the maximum degree that a vertex can have
subject to the condition that it is adjacent to at least one
vertex of equal or greater degree. ($\Delta_2$ is no more than the
maximum degree $\Delta$ of $G$.) \item Thus, in fact, we propose
here a \emphnew, \emphefficient coloring method that achieves
a number of colors \emphsatisfying (together) the known general
upper bounds on the chromatic number $\chi$. Our method is also
an alternative general way of \emphproving,
\emphconstructively, all these bounds. \item Finally, we show
how to strengthen our method (staying in polynomial time) so that
it avoids ``bad'' pure Nash equilibria (i.e. those admitting a
number of colors $k$ far away from $\chi$). In particular, we show
that our enhanced method colors \emphoptimally dense random
$q$-partite graphs (of fixed $q$) with high probability.
\enditemize |