On the road coloring problem
Proc. Amer. Math. Soc. 110 (1990), 1133-1135
Full-text PDF Free Access
Similar Articles |
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.
L. Adler, L.
Wayne Goodwyn, and Benjamin
Weiss, Equivalence of topological Markov shifts, Israel J.
Math. 27 (1977), no. 1, 48–63. MR 0437715
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
A. Hedlund, Endomorphisms and automorphisms of the shift dynamical
system, Math. Systems Theory 3 (1969), 320–375.
0259881 (41 #4510)
L. O’Brien, The road-colouring problem, Israel J. Math.
39 (1981), no. 1-2, 145–154. MR 617297
- R. L. Adler, L. W. Goodwyn, and B. Weiss, Equivalence of topological Markov shifts, Israel J. Math. 27 (1977), 49-63. MR 0437715 (55:10639)
- R. L. Adler and B. Weiss, Similarity of automorphisms of the torus, Mem. Amer. Math. Soc., no. 98, Amer. Math. Soc., Providence, RI, 1970. MR 0257315 (41:1966)
- G. A. Hedlund, Endomorphisms and automorphisms of the shift, Math. Systems Theory 3 (1969), 320-375. MR 0259881 (41:4510)
- G. L. O'Brien, The road-colouring problem, Israel J. Math. 39 (1981), 145-154. MR 617297 (82f:05048)
Retrieve articles in Proceedings of the American Mathematical Society
Retrieve articles in all journals
© Copyright 1990
American Mathematical Society