A vector space approach to the road coloring problem
Greg Budzban, Ph. Feinsilver · Russian Mathematics · 2010
Let G be a strongly connected, aperiodic, two-out digraph with adjacency matrix A . Suppose A = R + B are coloring matrices: that is, matrices that represent the functions induced by an edge-coloring of G . We introduce a matrix Δ = 1/2 ( R − B ) and investigate its properties. A number of useful conditions involving Δ which either are equivalent to or imply a solution to the road coloring problem are derived.