Road coloring conjecture

From Wikipedia, the free encyclopedia

The road coloring conjecture is a conjecture in graph theory and also in symbolic dynamics.

Let G be a finite directed graph where all the vertices have the same out-degree k. Then we can label the edges of G with k different letters so that all the edges going out from a vertex take a different label, and, for each vertex v in G, there exists some word W such that all paths in G presenting W terminate at v. This labeling is called a synchronizing coloring or a collapsible coloring.

For such a coloring to exist at all, it is necessary that G be both strongly connected and aperiodic.[1] The road coloring conjecture states that these two conditions are also sufficient for such a coloring to exist. Therefore, the road coloring conjecture can be stated briefly as:

Every finite strongly-connected aperiodic directed graph of uniform out-degree has a synchronizing coloring.

[edit] Example and intuition

The image to the right shows a directed graph on eight vertices in which each vertex has out-degree 2. (Each vertex in this case also has in-degree 2, but that is not necessary for a synchronizing coloring to exist.) The edges of this graph have been colored red and blue to create a synchronizing coloring.

For example, consider the vertex marked in yellow. No matter where in the graph you start, if you trace out the path "blue-blue-blue, blue-red-red, blue-red-red", you will end up at the yellow vertex. Similarly, if you trace out the path "blue-blue-red, blue-blue-red, blue-blue-red", you will always end up at the vertex marked in green, no matter where you started.

In the real world, this phenomenon would be as if you called a friend to ask for directions to his house, and he gave you a set of directions that worked no matter where you started from!

[edit] Partial results

The conjecture remains unproven, but there are many partial or special-case results, including the following:

• If G is a finite strongly-connected aperiodic directed graph with no multiple edges, and G contains a simple cycle of prime length which is a proper subset of G, then G has a synchronizing coloring. (G. L. O'Brien, "The road-coloring problem", Israel Journal of Mathematics, Vol. 39, 1981)

• If G is a finite strongly-connected aperiodic directed graph (multiple edges allowed) and every vertex has the same in-degree and out-degree k, then G has a synchronizing coloring. (Jarkko Kari, "Synchronizing finite automata on Eulerian digraphs", Theoretical Computer Science 295 (2003), 223–232)