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?
