Problem of the Week 966
All Roads Lead to Rome
Consider a directed graph having 11 vertices evenly spaced around a circle, and imagine these vertices labeled with cities such as Paris, Rome, Beijing, Jakarta, etc. At each vertex there are edges directed out to the two nearest neighbors. So the outdegree of every vertex is 2 and the indegree of every vertex is 2.
Find a coloring of the edges in two colors, red and blue, so that:
 Each vertex has a red edge leading out of it and a blue edge leading out of it.
 There is a single sequence of colors (such as "red, blue, red, red, blue, blue") such that following these instructions from any starting point leaves you in Rome.
Source: Bryan Shader, University of Wyoming (bshader@uwyo.edu)
Bryan (and others) have worked on many problems having to do with unique sequences of instructions in directed graphs with colored edges.
References for more on this topic are:
Adler, R. L., Goodwyn, L. W., Weiss, B., Equivalence of topological Markov shifts. Israel J. Math. 27 (1977), no. 1, 4863.
O'Brien, G. L., The roadcolouring problem. Israel J. Math. 39 (1981), no. 12, 145154.
Friedman, J., On the road coloring problem. Proc. Amer. Math. Soc. 110 (1990)
Gocka, E., Kirchherr, W., Schmeichel, E., A note on the roadcoloring conjecture. Ars Combin. 49 (1998), 265270.
© Copyright 2002 Stan Wagon. Reproduced with
permission.
