The Road Coloring Problem
Are you familiar with the road coloring problem ?
Suppose one is given a strongly connected digraph (that is, there is a directed path between any two vertices). One can think of the vertices of the graph as buildings, for example, and the directed arcs as unnamed, one-way roads connecting the buildings. Suppose, further, that in each building there is a person. Under what conditions can one color the roads, so that the same set of instructions allows each person to get to the same building ?
First, let’s take an instance.You’re driving to a friend’s place, and find yourself at a crossroads unfamiliar to you. So, you call up your friend from your mobile phone and ask for directions. She gives you a set of left/right/keep-straight directions. You thank her, hang up and follow the directions until you get to her place. As you drive up her driveway, you realize that you hadn’t even told her where you were when you called her. So, how did she manage to give you the right directions?This is an example of the road coloring problem.
A road-colouring is a colouring of the edges of a directed graph so that at each vertex, the outgoing edges get distinct colours. Such a colouring is called synchronizing if there is a sequence of colours (directions) that when followed takes you from any vertex to a pre-defined destination vertex. The road-colouring problem is to identify graphs that are synchronizable, i.e., graphs that admit a synchronizing road-colouring.