-->

• 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)

• Fast Facts

  1. Posed by Benjamin Weiss, Wayne Goodwin and Roy Adler while working at IBMThe Jerusalem Post: Russian immigrant solves math puzzle (February 8, 2008)
  2. Solved by Avraham TrahtmanIBM: Ponder This

• Related Mahalo Pages

  Mathematics | Avraham Trahtman | Trahtman Solution

Categories

• View History
• Discuss on the Message Board
• Embed this Page
• Share this page