July 2003
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: http://arxiv.org/abs/0709.0099.
If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com