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 out-degree of every vertex is 2 and the in-degree of every vertex is 2.

Find a coloring of the edges in two colors, red and blue, so that:

1. Each vertex has a red edge leading out of it and a blue edge leading out of it.
2. 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 ([email protected]) 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, 48-63.

O'Brien, G. L., The road-colouring problem. Israel J. Math. 39 (1981), no. 1-2, 145-154.

Friedman, J., On the road coloring problem. Proc. Amer. Math. Soc. 110 (1990)

Gocka, E., Kirchherr, W., Schmeichel, E., A note on the road-coloring conjecture. Ars Combin. 49 (1998), 265-270.