This article is cited in 2 papers

A vector space approach to the road coloring problem

G. Budzban, Ph. Feinsilver

Department of Mathematics, Southern Illinois University at Carbondale, Carbondale, IL, USA

Abstract: 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 $\Delta=\frac12(R-B)$ and investigate its properties. A number of useful conditions involving $\Delta$ which either are equivalent to or imply a solution to the road coloring problem are derived.

Keywords: digraph, synchronizing automaton, road coloring.

UDC: 519.713

Received: 21.10.2006

 English version: Russian Mathematics (Izvestiya VUZ. Matematika), 2010, 54:1, 10–15

Bibliographic databases:

• 
• 
•