Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS

Remote Access
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

PII: S 0002-9939(1990)0953004-8
Article copyright: © Copyright 1990 American Mathematical Society

Comments: Email Webmaster

© Copyright , American Mathematical Society
Contact Us · Sitemap · Privacy Statement

Connect with us Facebook Twitter Google+ LinkedIn Instagram RSS feeds Blogs YouTube Podcasts Wikipedia