of the same frog). The main drawback of this approach is that nodes with very near phases will be colored with different colors. As such small deviations usually occur when the number of nodes in the system increases, the algorithm does not obtain competitive results. This work was further extended by adding a parameter for setting a **priori the number of allowed** phases [28]. Experimentation shows that the system is able to find optimal solutions for small topologies, provided the optimal number of colors is known. **Note that in contrast to these** works, the algorithm that we propose aims for the minimization of the used number of colors without any prior knowledge about the optimal solution.

The literature also offers many works that consider distributed graph coloring from a theoretical point of view. Most of them concern upper bounds **for the coloring quality as**
well as the time complexity under different constraints. Hansen et al. [19] proposed the distributed largest-first (DLF) algorithm that runs in O(∆2logn**) communication rounds for**
arbitrary graphs and that was proven to provide good upper bounds for specific topologies. This algorithm was based on the largest-first **approach which consists in giving priority for**
choosing a color to the nodes with the highest degree (∆). This work was further extended by Kosowski and Kuszner [25] who reduced the time complexity to O(∆logn**log∆). These** authors also proved that some other approaches, like smallest-last or **dynamic-saturation**,
are not suitable for distributed environments. Later, in [34] Moscibroda and Wattenh¨ofer introduced an algorithm for obtaining O(∆)-colorings in O(δlogn**) time when considering** random geometric graphs and other well-known models for wireless multi-hop networks (no results are given for other topologies). Other theoretical **works which may be of interest** for the development of new algorithms are the game theoretic **approach for efficient graph**
coloring from Panagopoulou and Spirakis [36] and the work by **Kuhn and Wattenh¨ofer [26],**
which introduces a new lower bound on the number of colors used by algorithms that are restricted to one single communication round and a new lower **bound on the time complexity** of obtaining a O**(∆)-coloring of a graph.**

## 1.3 Organization Of The Paper

The rest of this paper is organized as follows. Section 2 describes the behavior of frogs in nature, which has inspired our algorithm. Moreover, existing models are outlined. In Section 3 the algorithm is introduced. An extensive experimental evaluation of the proposed algorithm is presented in Section 4. Finally, Section 5 is dedicated to **conclusions and the outline of**
future work.

## 2 Modelling The Calling Behavior Of Japanese Tree Frogs

Different studies (see, for example, [37]) have shown that male Japanese tree frogs use their calling to attract females. Apparently, females of this family of frogs can recognize the source of the calling in order to determine the current location of the corresponding male. A problem arises when two of these males are too close in space and communicate at the same time. In this case females are not able to properly recognize **both calls independently and are,**
therefore, unable to detect where the calls came from. For this reason, males have evolved to desynchronize their sounds in time. They achieve to uniformly distribute the distance between each pair of calls, which allows the females to locate the males they can hear, and to choose one. In fact, this behavior is a prime example for self-organization in nature.