from the literature. This algorithm was presented by Finocchi et al. in [13]. For simplicity, this algorithm will henceforth be referred to by Finocchi**. Unfortunately, the description of this** algorithm in the original article contains some ambiguities, which required us to make some decisions regarding certain aspects in the context of the re-implementation. Fortunately, our own implementation of the Finocci algorithm provides generally better results than the ones reported in [13]. This can be verified by comparing the results of the original implementation with the results of our re-implementation for the graph topologies that are used both in [13] and in the present paper.

In the following we present the results of three algorithms: **(1) Finocci [13], (2) FrogSim**,
which is the FrogSim algorithm without phase II, and (3) FrogSim, which is the complete FrogSim algorithm. In our opinion, the study of the results of FrogSim **is worthwhile,**
because it reflects the power of the frog-based model without **any additional improvements** of the refinement phase. We applied each of these three stochastic algorithms 100 times to each graph topology and report the best coloring found in all 100 runs, as well as the average quality of the best colorings found per run. The number of rounds necessary to reach these solutions is—due to space reasons—not included in the **result tables. However, it is**
important to note that algorithms such as Finocci and FrogSim, when used in sensor networks, are generally carried out continuously in a lower-level layer of the network. Therefore, the number of communication rounds necessary to reach the best solution are not that significant.

Instead our algorithm continually tries to improve the current solution. As an informative note, our algorithm requires, on average, 10.**34 communication rounds for finding its best**
solution in phase I. After entering phase II the best solution is reached, on average, after 3.46 communication rounds. In total, FrogSim requires, on average, 24.**33 communication rounds**
for finding its best solution. The algorithm of Finocchi et al. uses, on average, a comparable number of communication rounds (19.**83). It should be noted that, in the case of FrogSim,**
these numbers do not depend so much on the size of the network. **However, FrogSim takes**
generally more communication rounds for those graphs that have a larger number of edges.

After tuning by hand, we decided to use a communication round **limit of 100 rounds for**
FrogSim. Moreover, parameter K**, which specifies the number of communication rounds for** phase I, was always set to 80. As a last remark, note that the size of the messages used in FrogSim is constant (O**(1)). In other words, the message size does not depend on the network**
size. This is surely a desirably property of a distributed algorithm for graph coloring.

## 4.1 Results For Random Geometric Graphs

Random geometric graphs are popular models for sensor networks. Therefore, they are frequently used for the evaluation of algorithms developed for **such networks. They are generated**
by randomly distributing a set of n nodes in the [0, 1]2 area. Two vertices u and v are connected by an edge, if and only if d(u, v) ≤ r, where d(., .) is the Euclidean distance and r > 0 is a threshold. More specifically, the three algorithms were **applied to 40 random geometric** graphs with n ∈ {20, 50, 100, 200} and r = 0.05.

Table 1 presents the results obtained for this set of instances. In particular, the first column shows the names of the instances and the second column provides a triple (n, ∆, χ), where n is the number of nodes, ∆ the maximum degree, and χ **the chromatic number of** the corresponding graph. In case of a question mark, the chromatic number is not known. The following three groups of columns provide the results obtained by the three algorithms.