On the road coloring problem

Author:
Joel Friedman

Journal:
Proc. Amer. Math. Soc. **110** (1990), 1133-1135

MSC:
Primary 05C15

MathSciNet review:
953004

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: Let be a strongly connected, aperiodic, directed graph having outdegree 2 at each vertex. A *red-blue coloring* of is a coloring of the edges with the colors red and blue such that each vertex has one red edge and one blue edge leaving it. Given such a coloring, we define by iff there is a red edge from to . Similarly we define . is said to be collapsible if some composition of 's and 's maps to a single vertex. The road coloring problem is to determine whether has a collapsible coloring. It has been conjectured that all such have a collapsible coloring. Since has outdegree 2 everywhere and is strongly connected, the adjacency matrix, , of has a positive left eigenvector with eigenvalue 2 , i.e. . Furthermore, we can assume that 's components are integers with no common factor. We call the *weight* of . Let , defined to be the weight of the graph. We will prove that if has a simple cycle of length relatively prime to , then is collapsibly colorable.

**[1]**Roy L. Adler, L. Wayne Goodwyn, and Benjamin Weiss,*Equivalence of topological Markov shifts*, Israel J. Math.**27**(1977), no. 1, 48–63. MR**0437715****[2]**Roy L. Adler and Benjamin Weiss,*Similarity of automorphisms of the torus*, Memoirs of the American Mathematical Society, No. 98, American Mathematical Society, Providence, R.I., 1970. MR**0257315****[3]**G. A. Hedlund,*Endomorphisms and automorphisms of the shift dynamical system*, Math. Systems Theory**3**(1969), 320–375. MR**0259881****[4]**G. L. O’Brien,*The road-colouring problem*, Israel J. Math.**39**(1981), no. 1-2, 145–154. MR**617297**, 10.1007/BF02762860

Retrieve articles in *Proceedings of the American Mathematical Society*
with MSC:
05C15

Retrieve articles in all journals with MSC: 05C15

Additional Information

DOI:
https://doi.org/10.1090/S0002-9939-1990-0953004-8

Article copyright:
© Copyright 1990
American Mathematical Society