Distributed Graph Coloring: An Approach Based on the Calling Behavior of
  Japanese Tree Frogs
  Graph coloring, also known as vertex coloring, considers the problem of
assigning colors to the nodes of a graph such that adjacent nodes do not share
the same color. The optimization version of the problem concerns the
minimization of the number of used colors. In this paper we deal with the
problem of finding valid colorings of graphs in a distributed way, that is, by
means of an algorithm that only uses local information for deciding the color
of the nodes. Such algorithms prescind from any central control. Due to the
fact that quite a few practical applications require to find colorings in a
distributed way, the interest in distributed algorithms for graph coloring has
been growing during the last decade. As an example consider wireless ad-hoc and
sensor networks, where tasks such as the assignment of frequencies or the
assignment of TDMA slots are strongly related to graph coloring.
  The algorithm proposed in this paper is inspired by the calling behavior of
Japanese tree frogs. Male frogs use their calls to attract females.
Interestingly, groups of males that are located nearby each other desynchronize
their calls. This is because female frogs are only able to correctly localize
the male frogs when their calls are not too close in time. We experimentally
show that our algorithm is very competitive with the current state of the art,
using different sets of problem instances and comparing to one of the most
competitive algorithms from the literature.
