Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
   
Mobile Device Pairing
Green Open Access
Proceedings of the American Mathematical Society
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 Free Access

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

DOI: http://dx.doi.org/10.1090/S0002-9939-1990-0953004-8
PII: S 0002-9939(1990)0953004-8
Article copyright: © Copyright 1990 American Mathematical Society