On the road coloring problem
Joel I. Friedman · Proceedings of the American Mathematical Society · 1990
Let G = ( V , E ) G = (V,E) be a strongly connected, aperiodic, directed graph having outdegree 2 at each vertex. A red-blue coloring of G 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 → V R:V \to V by R ( v ) = w R(v) = w iff there is a red edge from v v to w w . Similarly we define B : V → V B:V \to V . G G is said to be collapsible if some composition of R R ’s and B B ’s maps V V to a single vertex. The road coloring problem is to determine whether G G has a collapsible coloring. It has been conjectured that all such G G have a collapsible coloring. Since G G has outdegree 2 everywhere and is strongly connected, the adjacency matrix, A A , of G G has a positive left eigenvector