Hosted by The Math Forum
Problem of the Week 966
All Roads Lead to Rome
MacPoW Home ||
Forum PoWs ||
Teachers' Place ||
Student Center ||
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:
- 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 (firstname.lastname@example.org)
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.
© Copyright 2002 Stan Wagon. Reproduced with
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.