A note on the network coloring game: A randomized distributed (Δ + 1)-coloring algorithm

• Published in: Information processing letters 2023-08, Vol.182, p.106385, Article 106385
• Main Authors: Fryganiotis, Nikolaos, Papavassiliou, Symeon, Pelekis, Christos
• Format: Article
• Language: English
• Subjects: Distributed computing; Games on graphs; Graph coloring; Greedy algorithms; Symmetric strategies
• ISSN: 0020-0190; 1872-6119
• DOI: 10.1016/j.ipl.2023.106385

The network coloring game has been proposed in the literature of social sciences as a model for conflict-resolution circumstances. The players of the game are the vertices of a graph with n vertices and maximum degree Δ. The game is played over rounds, and in each round all players simultaneously choose a color from a set of available colors. Players have local information of the graph: they only observe the colors chosen by their neighbors and do not communicate or cooperate with one another. A player is happy when she has chosen a color that is different from the colors chosen by her neighbors, otherwise she is unhappy, and a configuration of colors for which all players are happy is a proper coloring of the graph. It has been shown in the literature that, when the players adopt a particular greedy randomized strategy, the game reaches a proper coloring of the graph within O(log⁡(n)) rounds, with high probability, provided the number of colors available to each player is at least Δ+2. In this note we show that a modification of the aforementioned greedy strategy yields likewise a proper coloring of the graph, provided the number of colors available to each player is at least Δ+1. •We investigate the network coloring game, which was introduced as a model for conflict-resolution circumstances.•A strategy of the players exists that converges to equilibrium in O(log⁡n) rounds, provided each player has enough colors.•We improve upon the above-mentioned strategy by reducing the required number of colors by one.•We obtain a distributed algorithm for the (Δ+1)-coloring problem that requires no exchange of information among vertices.