Road coloring theorem

The road coloring theorem states that every finite, strongly connected directed graph with constant outdegree and cycle-length greatest common divisor one has an edge coloring whose associated automaton is synchronizing.

Connect

Synchronizing automaton: A finite automaton is synchronizing if some input word sends every state to the same state. The coloring promised by the theorem makes the graph's automaton synchronizing.
Boris Weisfeiler: Boris Weisfeiler was a mathematician who posed the road coloring problem in the 1970s. His question supplied the problem that the theorem answers.
Finite automaton: A finite automaton is a finite set of states equipped with transitions driven by input symbols. A coloring assigns input symbols to edges and thereby defines the automaton in the theorem.
Synchronizing word: A synchronizing word is an input sequence that sends every state of an automaton to one state. The theorem's coloring ensures that at least one such word exists.
Road coloring problem: The road coloring problem asks whether a directed graph satisfying specified regularity conditions can be edge-colored to form a synchronizing automaton. The theorem resolves this existence problem for graphs with cycle-length gcd one.
Avraham Trahtman: Avraham Trahtman is a mathematician who proved the road coloring theorem in 2007. His proof established the theorem in its full stated generality.
Directed graph: A directed graph consists of vertices joined by edges with specified directions. The theorem begins with a directed graph whose edges are to be colored.
Synchronizing automata: Synchronizing automata are finite automata that admit an input word merging all states into one. The theorem constructs an automaton in this broader class from a suitable graph.
Strongly connected graph: A directed graph is strongly connected when every vertex can reach every other vertex by a directed path. Strong connectivity is one of the theorem's structural hypotheses.
Trahtman's algorithm: Trahtman's algorithm constructs a synchronizing coloring for a finite strongly connected aperiodic directed graph of constant outdegree. It gives a constructive route to the coloring whose existence the theorem guarantees.