The Road Coloring Problem, or Road Coloring Conjecture, is a mathematical problem associated with the field of Graph Theory. It posits that, given a finite number of routes to a destination, a set of directions can be given that will lead to that destination from any given starting point. For instance, if following blue and red color-coded lines on a two-dimensional graphed shape, a path to a destination point from any starting point can always be given in the form of a sometimes long and inefficient, but ultimately correct, combination of 'blue' and 'red' instructions. Many mathematicians have attempted to prove this conjecture since it was first posed in 1970.

Israeli mathematician Avraham Trahtman proved the mathematical riddle in 2007.The Jerusalem Post: Russian immigrant solves math puzzle (February 8, 2008)