Group for Research in Decision Analysis

The Road Coloring Problem

Romain Absil Université de Mons, Belgium

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.