# The road coloring problem

@article{Trahtman2007TheRC, title={The road coloring problem}, author={A. N. Trahtman}, journal={Israel Journal of Mathematics}, year={2007}, volume={172}, pages={51-60} }

A synchronizing word of a deterministic automaton is a word in the alphabet of colors (considered as letters) of its edges that maps the automaton to a single state. A coloring of edges of a directed graph is synchronizing if the coloring turns the graph into a deterministic finite automaton possessing a synchronizing word. The road coloring problem is the problem of synchronizing coloring of a directed finite strongly connected graph with constant outdegree of all its vertices if the greatest… Expand

#### Topics from this paper

#### 105 Citations

The Road Coloring and Cerny Conjecture

- Computer Science, Mathematics
- Stringology
- 2008

The positive solution of the road coloring problem is presented and some consequences on the length of the synchronizing word are discussed. Expand

A Subquadratic Algorithm for Road Coloring

- Mathematics
- 2008

The synchronizing word of a deterministic automaton is a word in the alphabet of colors (considered as letters) of its edges that maps the automaton to a single state. A coloring of edges of a… Expand

Ja n 20 08 A Subquadratic Algorithm for Road Coloring

- 2008

The synchronizing word of a deterministic automaton is a word in the alphabet of colors (considered as letters) of its edges that maps the automaton to a single state. A coloring of edges of a… Expand

An algorithm for road coloring

- Mathematics, Computer Science
- 2008

A polynomial time algorithm of O(n3) complexity in the worst case and quadratic in the majority of studied cases for the road coloring of the considered graph is presented below. Expand

An algorithm for road coloring

- Mathematics
- 2012

A coloring of edges of a finite directed graph turns the graph into a finite-state automaton. A synchronizing word of a deterministic automaton is a word in the alphabet of colors of its edges… Expand

The Visualization of the Road Coloring Algorithm in the package TESTAS

- Mathematics, Computer Science
- ArXiv
- 2009

A polynomial time algorithm of the road coloring has been based on recent positive solution of this old famous problem and the new visualization program is used for demonstration of the algorithm as well as for visualization of the transition graph of any finite automaton. Expand

A partially synchronizing coloring

- Mathematics
- 2010

Given a finite directed graph, a coloring of its edges turns the graph into a finite-state automaton. A k-synchronizing word of a deterministic automaton is a word in the alphabet of colors at its… Expand

Synchronizing Road Coloring

- Mathematics
- 2008

The synchronizing word of a deterministic automaton is a word in the alphabet of colors (considered as letters) of its edges that maps the automaton to a single state. A coloring of edges of a… Expand

Linear Visualization of a Road Coloring Algorithm

- 2009

A problem of a visual image of a directed finite graph has appeared in the study of the road coloring conjecture. Given a finite directed graph, a coloring of its edges turns the graph into… Expand

On Synchronizing Colorings and the Eigenvectors of Digraphs

- Mathematics, Computer Science
- MFCS
- 2016

It is shown that a vector v has no partition of coordinates into blocks of equal sum if and only if all colorings of the digraphs associated with v are synchronizing. Expand

#### References

SHOWING 1-10 OF 38 REFERENCES

Cycles of relatively prime length and the road coloring problem

- Mathematics
- 2001

We give a partial answer to theroad coloring problem, a purely graphtheoretical question with applications in both symbolic dynamics and automata theory. The question is whether for any positive… Expand

A Note on Synchronized Automata and Road Coloring Problem

- Computer Science
- Int. J. Found. Comput. Sci.
- 2001

A relabeling method is introduced which can be used for a large class of automata to improve their "degree of synchronization" and allows, for example, to formulate the Road Coloring Conjecture in several equivalent ways. Expand

A NOTE ON SYNCHRONIZED AUTOMATA AND ROAD COLORING PROBLEM

- Mathematics
- 2002

We consider the problem of labeling a directed multigraph so that it becomes a synchronized finite automaton, as an ultimate goal to solve the famous Road Coloring Conjecture, cf. [1,2]. We introduce… Expand

Notable trends concerning the synchronization of graphs and automata

- Computer Science
- Electron. Notes Discret. Math.
- 2006

An effective program for search of automata with minimal reset word of relatively great length has studied all automata of size n ≤ 10 for q = 2 (q size of alphabet) and ofsize n ≤ 7 for q ≤ 4 and there are no contradictory examples for the Černy conjecture in this class of Automata. Expand

A Note on the Road-Coloring Conjecture

- Computer Science, Mathematics
- Ars Comb.
- 1998

It is shown that, if the outdegree of every edge in an n-vertex digraph is δ = ω(logn), a road-coloring for the graph exists and an equivalent re-statement of the conjecture is given in terms of the cross-product of two graphs. Expand

A Min-Max theorem about the Road Coloring Conjecture

- Mathematics
- 2005

The Road Coloring Conjecture is an old and classical conjecture e posed in Adler and Weiss (1970); Adler et al. (1977). Let $G$ be a strongly connected digraph with uniform out-degree $2$. The Road… Expand

On two Combinatorial Problems Arising from Automata Theory

- Mathematics
- 1983

We present some partial results on the following conjectures arising from automata theory. The first conjecture is the triangle conjecture due to Perrin and Schiitzenberger. Let A ={a, b } be a… Expand

The road-colouring problem

- Mathematics
- 1981

LetG be a finite directed graph which is irreducible and aperiodic. Assume each vertex ofG leads to at least two other vertices, and assumeG has a cycle of prime length which is a proper subset ofG.… Expand

Many-Valued Truth Functions, Cerny's Conjecture and Road Coloring

- Mathematics, Computer Science
- Bull. EATCS
- 1999

Interconnections between many-valued truth functions and functions defined by finite deterministic automata is investigated, finding results in one theory, such as those concerning self-conjugacy of truth functions, can be applied in the other theory. Expand

Synchronizing finite automata on Eulerian digraphs

- Computer Science, Mathematics
- Theor. Comput. Sci.
- 2003

This paper proves Fr?erný's conjecture and the road coloring problem are two open problems concerning synchronization of finite automata in the special case that the vertices have uniform in- and outdegrees. Expand