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 

may be you should specify your problem a little.
i mean graph parameters & color quantity
and may be... not :p
In simplicity: just do a topological sort(since there are no cycles), start from the furthest child node and work backwards through the sort. O(|V|+|E|) The solution will be unique, provided sane assumptions - you really didn't state too much detail.

In general though, you've got a mess. Just imagine an odd length cycle with a set of rules that will try to make the coloring alternate between white and black as you go around the cycle. There is no solution so no convergence.

but for your algorithm I expect it will converge in O(g(C)|V|^2), where g(c) is some function of the number of colors, or not at all. The funny question is in a given cycle does finding a solution depend on the order in which you process the nodes? I think it does - so then the problem is interesting.

What's this problem for?
if you can define an appropriate field F that describes your coloring scheme, then if the adjacency matrix A has any real eigenvalues of magnitude greater than or equal to 1 or any complex values in the closed right half plane, then you aren't guaranteed convergence.
incidentally, this method only cares that your graph is connected --- it correctly accounts for cycles.