Groupe d’études et de recherche en analyse des décisions

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.