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. (O'Brien 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. (Kari 2003)
[edit] References
- Jarkko Kari, "Synchronizing finite automata on Eulerian digraphs", Theoretical Computer Science 295 (2003), 223–232.
- G. L. O'Brien, "The road-coloring problem", Israel Journal of Mathematics, Vol. 39, 1981.
