An Efficient and Robust Distributed Vertex Coloring Algorithm in Wireless Networks

Abstract The distributed vertex coloring is one of the most intensively studied problem in graph theory with many applications in computer networks.We propose a deterministic distributed algorithm for this problem in wireless networks.The algorithm's run-time is divided into rounds.In each round, every uncolored vertex or at least one of its neighbors obtains a color equal to the round number and informs its neighbors of the taken color with a 1-bit message. Therefore, the bit complexity is minimum. Moreover, the set of colored vertices is a maximal independent set (MIS), and the maximum number of colors or rounds equals the maximum number of MISs that cover the graph's vertices. It is bounded by the maximum vertex degree and also the radius of the graph.This is the first algorithm that uses a lower bound on the number of colors for every graph.In the case of trees, the logarithm of the number of vertices is another upper bound for it. Finally, we propose another algorithm for 2-coloring, and the number of rounds is bounded by the diameter of the tree.