On the Road Coloring Problem

For our evaluation during the the M2 course Recent Topics in Graph Theory, we had to study a specific issue and realize a small survey on the matter, by summing up several research papers and detailling on or two technical points along the way. I devoted myself to the road coloring problem, which deals with edge coloring of a graph, the existence of a synchronizing word in a finite automaton, and cycles in a graph of relativeley prime lengths. You can find my report here, as well as the slides used for my oral presentation.