*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"?

kaunovJuly 4 2008, 16:09:50 UTC 8 years ago

i mean graph parameters & color quantity

and may be... not :p

wanton_adonisJuly 4 2008, 19:06:15 UTC 8 years ago

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?

notquitezeusJuly 4 2008, 19:27:43 UTC 8 years ago

notquitezeusJuly 4 2008, 19:28:22 UTC 8 years ago