IBM Research | Ponder This | July 2003 solutions
Skip to main content

July 2003

<<June July August>>

As I mentioned, this is unsolved.
Existing literature includes:

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.

Update (2009): The conjunction was proved by Avraham N. Trahtman:

If you have any problems you think we might enjoy, please send them in. All replies should be sent to: