Eugene Kirpichov (antilamer) wrote in algorithms,
Eugene Kirpichov

Convergence of graph colouring

I am coloring a graph's nodes, based on a set of initial conditions and rules of the form "if colors of a node's neighbours are like this, then color of the node is that": so, a cellular automaton on the graph.
For simplicity, let us consider the graph to be acyclic and restrict the rules so that a node's color depends only on the colors of its child nodes.

What are the methods of exploring convergence and soundness of such a system of rules?

To put it easier, how to know, for a given system of rules, whether there exists a unique coloring satisfying them, and whether it is reachable by the following algorithm: "take any node, apply rules to it, repeat until convergence"?
  • Post a new comment


    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded