This question considers the design of a deterministic self-stabilizing algorithm for vertex coloring in uniform anonymous networks. Uniform anonymous networks do not have distinguished nodes and all nodes run identical programs without access to globally unique node identifiers. The problem vertex coloring requires the assignment of an integer, called color, to every node in the network. These colors are selected from a predefined set, named palette. In this question, we assume that the palette includes at least Δ+1 colors, and thus, selecting an optimal number of colors is not relevant.

Consider the case in which the network topology is a general graph. Supposedly then, there is no self-stabilizing deterministic algorithm for vertex coloring in general graphs.

This was what my teacher in my distributed systems class mentioned briefly during a lecture, but never went into detail about. Why is there no self-stabilizing determinsitic algorithm for vertex coloring in general graphs?

  • $\begingroup$ Have you tried to prove this? It might help to consider a graph with just two nodes and one edge. Now let these two nodes execute the same deterministic algorithm in lock step. How could they end up with different colours? $\endgroup$
    – Kai
    Oct 25, 2023 at 12:14


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.