 |
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.
|