Road coloring problem
Teorema del coloreo de carreteras
- Date
- 2009 · confidence high
- Place
- Ramat Gan, Tel Aviv District, Israel
- Credited to
- Avraham Trahtman (conjectured by Roy Adler and Benjamin Weiss)
- Field
- Knowledge & symbols
What was discovered
A theorem of graph theory and symbolic dynamics proving that every strongly connected, aperiodic directed graph with constant out-degree admits an edge labeling that synchronizes the path to any vertex from any other; conjectured by Roy Adler and Benjamin Weiss and proved by Avraham Trahtman in 2009.
What it led to
- Applications in symbolic dynamics
- Relevance to synchronizing instructions in robotics and networking
- Resolved a decades-old open combinatorial conjecture