Road Coloring Problem

Until recently, the Road Coloring theorem was known as the Road Coloring conjecture. This means that it was a hypothesis that had not yet been proven by anyone. Avraham Trahtman proved it in September 2007. It therefore became a mathematical theorem. The conjecture of this problem was first made in 1970 by Benjamin Weiss and Roy Adler.

The Road Coloring theorem is part of a branch of mathematics called graph theory. Graphs are a bit like networks, maps or grids. They can be used to represent the structure of a website, road networks, and other situations which can be modeled by a graph.

Graph theory is the study of graphs; mathematical structures used to model pairwise relations between objects from a certain collection. A “graph” in this context refers to a collection of vertices or ‘nodes’ and a collection of edges that connect pairs of vertices. A graph may be undirected, meaning that there is no distinction between the two vertices associated with each edge, or its edges may be directed from one vertex to another.

In layman’s terms, the issue is to find out if by using instructions, you can reach or locate an object or destination from any point within a network. Of course, here when we use network, we mean the non-mathematical definition of a network. A network in graph theory is a digraph with weighted edges, such as the lengths of a road in a road graph representation. With networks, you can analyze traffic networks, transportation networks and other such type of networks.

The solution appears to be completely counterintuitive. For example, it can be expressed as the following analogy. Whether a man who arrives in a city without street names to visit a friend and telephones for help, could be given directions which would work wherever he was at the time.

Consider the above directed graph. Each vertex (node in the graph) has an out-degree of 2. That simply means that two paths go out from each vertex. Each vertex also has an in-degree of 2. Two paths always lead to each vertex. However, for a synchronizing coloring to exist, we need a constant out-degree for all its vertices. In this case, it’s 2. The edges (or paths) have been colored in red and blue to create a synchronizing coloring (a type of graph labeling).

Graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called “colors” to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices of a graph such that no two adjacent vertices share the same color; this is called a vertex coloring. Similarly, an edge coloring assigns a color to each edge so that no two adjacent edges share the same color, and a face coloring of a planar graph assigns a color to each face or region so that no two faces that share a boundary have the same color.

Consider the vertex marked in yellow. No matter on which vertex you start, if you traverse all nine edges in the walk “blue-red-red—blue-red-red—blue-red-red”, you will end up at the yellow vertex. Similarly, if you will always end up at the green vertex by using this walk “blue-blue-red—blue-blue-red—blue-blue-red”.

The road coloring theorem states that for a certain category of directed graphs, it is always possible to create a synchronizing coloring. The graph needs to be strongly connected and aperiodic.

A directed graph is said to be aperiodic if there is no integer k > 1 that divides the length of every cycle of the graph. Equivalently, a graph is aperiodic if the greatest common divisor of the lengths of its cycles is one; this greatest common divisor for a graph G is called the period of G.

A directed graph is called strongly connected if for every pair of vertices u and v there is a path from u to v and a path from v to u. The strongly connected components (SCC) of a directed graph are its maximal strongly connected subgraphs. These form a partition of the graph. If each strongly connected component is contracted to a single vertex, the resulting graph is a directed acyclic graph.

Synchronizing coloring corresponds to the synchronizing word in deterministic finite state automaton theory, a field of research stemming from combinatorics.

The road coloring problem is important in automata theory. It makes the behavior of an automaton resistant against input errors. Once an error is detected, a synchronizing word can reset the automaton to its original state, as if no error had occurred.

A coloring of a directed finite graph is synchronizing if the said coloring turns the graph into a deterministic finite state automaton processing a synchronizing word.

In his paper, Trahtman uses 7 lemmas that he proves and three theorems to lead to his final theorem, which proves the road coloring conjecture. In mathematics, theorems can often be deduced and easily proven from lemmas. Lemmy 7 the most significant.

The set of all outgoing edges of a vertex is called a bunch if all these edges are incoming edges of only one vertex.

A spanning subgraph S is a subgraph of an aperiodic finite strongly connected directed graph Γ all of the vertices of Γ belong to S and exactly one outgoing edge of every vertex of Γ.

A synchronizing pair of states p and q of an automaton is called stable if for any word u the pair pu, qu is also synchronizing.

Theorem 2 [J. Kari. Synchronizing finite automata on Eulerian digraphs, Theoretical Computer Science 295 (2003), 223–232]

Let us consider a coloring of aperiodic finite strongly connected directed graph Γ. The stability of states is a binary relation on the set of states of the obtained automaton; we denote this relation by ρ. Then ρ is a congruence relation, Γ/ρ is an aperiodic finite strongly connected directed graph and a synchronizing coloring of Γ/ρ implies synchronizing recoloring of Γ.

Lemma 7
Let any vertex of an aperiodic finite strongly connected directed graph Γ have no two incoming bunches. Then Γ has a spanning subgraph such that all its vertices of maximal positive level belong to one non-trivial tree.

This leads to his third theorem in this paper.

Theorem 3
Any aperiodic finite strongly connected directed graph has a coloring with stable couples.

Which leads him to conclude his final theorem, which is inferred from theorem 3 and 2.

Theorem 4
Every aperiodic finite strongly connected directed graph has synchronizing coloring.

The proof is complex for laymen to understand. Mathematicians specializing in graph theory can fully grasp the implications and the proofs. As a mathematics student, most of it is above my level of understanding of graph theory and combinatorics, but I can partly understand it at times. Here is a link to the proof.

As mentioned before, the result is counterintuitive, but the road coloring problem is for a finite directed graph that is strongly connected and aperiodic, which doesn’t make it any less difficult to prove. Over a hundred mathematicians over the last 37 years have tried to prove this problem. Avraham Trahtman is a 63 year old professor of mathematics at Bar-Ilan University (Israel).

Author: range

I'm mathematician/IT strategist/blogger from Canada living in Taipei.

One thought on “Road Coloring Problem”

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s