On the Roadmap Coloring Problem
  • Postscript version.
  • Dvi version.
  • PDF version.

  • Abstract:

    Let $G=(V,E)$ be a strongly connected, aperiodic, directed graph having outdegree $2$ at each vertex. A {\em 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\colon V\rightarrow V$ by $R(v) = w$ iff there is a red edge from $v$ to $w$. Similarly we define $B\colon V\rightarrow 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=\left( w(v_1),\ldots,w(v_n)\right)$ 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 {\em weight} of $v$. Let $W\equiv \sum_{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.