Variants of the road coloring problem 
Marie-Pierre B´eal and Dominique Perrin 
January 28, 2009 
The road coloring problem asks to find a coloring of a graph which turns it 
into a synchronized deterministic automaton. It was shown by A. Trahtman [3] 
to have a solution for any aperiodic irreducible graph of constant outdegree, 
solving a longstanding conjecture [1]. The theorem implies in particular that 
any Huffman code can be chosen to be synchronized. In this talk, we will discuss 
several alternative methods to choose such a synchronized optimal prefix code. 
We will also mention a variant which uses an earlier result [2] to treat the case 
of unequal weigths on the symbols.
References
[1] Roy L. Adler, L. Wayne Goodwyn, and Benjamin Weiss. Equivalence of 
topological Markov shifts. Israel J. Math., 27(1):48–63, 1977. 
[2] Dominique Perrin and Marcel-Paul Sch¨utzenberger. Synchronizing prefix 
codes and automata and the road coloring problem. In Symbolic dynamics 
and its applications, volume 135 of Contemp. Math., pages 295–318. Amer. 
Math. Soc., 1992. 
[3] A. N. Trahtman. The road coloring problem. To appear in Israel J. Math.