On the road coloring problem
Author:
Joel Friedman
Journal:
Proc. Amer. Math. Soc. 110 (1990), 11331135
MSC:
Primary 05C15
MathSciNet review:
953004
Fulltext 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 redblue 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
(55 #10639)
 [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
(41 #1966)
 [3]
G.
A. Hedlund, Endomorphisms and automorphisms of the shift dynamical
system, Math. Systems Theory 3 (1969), 320–375.
MR
0259881 (41 #4510)
 [4]
G.
L. O’Brien, The roadcolouring problem, Israel J. Math.
39 (1981), no. 12, 145–154. MR 617297
(82f:05048), http://dx.doi.org/10.1007/BF02762860
 [1]
 R. L. Adler, L. W. Goodwyn, and B. Weiss, Equivalence of topological Markov shifts, Israel J. Math. 27 (1977), 4963. MR 0437715 (55:10639)
 [2]
 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)
 [3]
 G. A. Hedlund, Endomorphisms and automorphisms of the shift, Math. Systems Theory 3 (1969), 320375. MR 0259881 (41:4510)
 [4]
 G. L. O'Brien, The roadcolouring problem, Israel J. Math. 39 (1981), 145154. MR 617297 (82f:05048)
Similar Articles
Retrieve articles in Proceedings of the American Mathematical Society
with MSC:
05C15
Retrieve articles in all journals
with MSC:
05C15
Additional Information
DOI:
http://dx.doi.org/10.1090/S00029939199009530048
PII:
S 00029939(1990)09530048
Article copyright:
© Copyright 1990
American Mathematical Society
