The Road Coloring Problem
Romain Absil – Université de Mons, Belgique
This seminar is about the road coloring problem in graph theory. This problem of synchronisation was first conjectured in 1970 by Adler, Goodwyn et Weiss and finally solved by A. Trahtman in 2007. After a short introduction of the domain of synchronisation, we will discuss about theorems and algorithms granting us to quickly find a solution.