Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)



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

Abstract | References | Similar Articles | Additional Information

Abstract: Let $ G = (V,E)$ be a strongly connected, aperiodic, directed graph having outdegree 2 at each vertex. A red-blue coloring of $ G$ 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 $ R:V \to V$ by $ R(v) = w$ iff there is a red edge from $ v$ to $ w$. Similarly we define $ B:V \to V$ . $ G$ is said to be collapsible if some composition of $ R$'s and $ B$'s maps $ V$ to a single vertex. The road coloring problem is to determine whether $ G$ has a collapsible coloring. It has been conjectured that all such $ G$ have a collapsible coloring. Since $ G$ has outdegree 2 everywhere and is strongly connected, the adjacency matrix, $ A$, of $ G$ has a positive left eigenvector $ w = (w({v_1}), \ldots ,w({v_n}))$ with eigenvalue 2 , i.e. $ wA = 2w$. Furthermore, we can assume that $ w$'s components are integers with no common factor. We call $ w(v)$ the weight of $ v$. Let $ W \equiv {\Sigma _{v \in V}}w(v)$, defined to be the weight of the graph. We will prove that if $ G$ has a simple cycle of length relatively prime to $ W$, then $ G$ is collapsibly colorable.

References [Enhancements On Off] (What's this?)

Similar Articles

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

Retrieve articles in all journals with MSC: 05C15

Additional Information

Article copyright: © Copyright 1990 American Mathematical Society

American Mathematical Society