Geodesic
A vector space approach to the road coloring problem
Izvestiâ vysših učebnyh zavedenij. Matematika, no. 1 (2010), pp. 14-20.

Voir la notice de l'article provenant de la source Math-Net.Ru

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. 
@article{IVM_2010_1_a2,
     author = {G. Budzban and Ph. Feinsilver},
     title = {A vector space approach to the road coloring problem},
     journal = {Izvesti\^a vys\v{s}ih u\v{c}ebnyh zavedenij. Matematika},
     pages = {14--20},
     publisher = {mathdoc},
     number = {1},
     year = {2010},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/IVM_2010_1_a2/}
}
TY  - JOUR
AU  - G. Budzban
AU  - Ph. Feinsilver
TI  - A vector space approach to the road coloring problem
JO  - Izvestiâ vysših učebnyh zavedenij. Matematika
PY  - 2010
SP  - 14
EP  - 20
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/IVM_2010_1_a2/
LA  - ru
ID  - IVM_2010_1_a2
ER  - 
%0 Journal Article
%A G. Budzban
%A Ph. Feinsilver
%T A vector space approach to the road coloring problem
%J Izvestiâ vysših učebnyh zavedenij. Matematika
%D 2010
%P 14-20
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/IVM_2010_1_a2/
%G ru
%F IVM_2010_1_a2
G. Budzban; Ph. Feinsilver. A vector space approach to the road coloring problem. Izvestiâ vysših učebnyh zavedenij. Matematika, no. 1 (2010), pp. 14-20. http://geodesic.mathdoc.fr/item/IVM_2010_1_a2/

[1] Adler R. L., Goodwyn L. W., Weiss B., “Equivalence of topological Markov shifts”, Israel J. Math., 27:1 (1977), 49–63 | DOI | MR | Zbl

[2] Culik K., Kari J., Karhumäki J., “A note on synchronized automata and road coloring problem”, Internat. J. Found. Comp. Sci., 13:3 (2002), 459–471 | DOI | MR | Zbl

[3] Budzban G., Feinsilver P., “Completely simple semigroups, Lie algebras, and the road coloring problem”, Semigroup Forum, 74:2 (2007), 206–226 | DOI | MR | Zbl

[4] Klifford A., Preston G., Algebraicheskaya teoriya polugrupp, Mir, M., 1972, 285 pp. | Zbl

[5] Carbone A., “Cycles of relatively prime length and the road coloring problem”, Israel J. Math., 123:1 (2001), 303–316 | DOI | MR | Zbl

[6] Jonoska N., Suen S., “Monocyclic decomposition of graphs and the road coloring problem”, Congr. Numer., 110 (1995), 201–209 | MR | Zbl

[7] O'Brien G. L., “The road coloring problem”, Israel J. Math., 39:1–2 (1981), 145–154 | DOI | MR

[8] Budzban G., Mukherjea A., “A semigroup approach to the Road Coloring Problem”, Contemp. Math., 261 (2000), 195–207 | MR | Zbl

[9] Friedman J., “On the road coloring problem”, Proc. Amer. Math. Soc., 110:4 (1990), 1133–1135 | DOI | MR | Zbl

[10] Budzban G., “Semigroups and the generalized road coloring problem”, Semigroup Forum, 69:2 (2004), 201–208 | DOI | MR | Zbl

[11] Hegde R., Jain K., “A min-max theorem about the road coloring conjecture”, Discrete Math. Theoret. Comput. Sci., AE (2005), 279–284

[12] Kari J., “Synchronizing finite automata on Eulerian digraphs”, Theoret. Comput. Sci., 295 (2003), 223–232 | DOI | MR | Zbl

[13] Trahtman A. N., “The road coloring problem”, Israel. J. Math. (to appear)