Road Coloring Problem Solved

ArieKremen writes "Israeli Avraham Trakhtman, a Russian immigrant mathematician who had been employed as a night watchman, has solved the Road Coloring problem. First posed in 1970 by Benjamin Weiss and Roy Adler, the problem posits that given a finite number of roads, one should be able to draw a map, coded in various colors, that leads to a certain destination regardless of the point of origin. The 63-year-old Trakhtman jotted down the solution in pencil in 8 pages. The problem has real-world implementation in message and traffic routing."

Comments

link to solution

[sammy baby]

Link to solution is busted. Find it here.

Please translate

[schlick]

Can somebody say this in plainer language?

"Every finite strongly-connected aperiodic directed graph of uniform out-degree has a synchronizing coloring"

I'm simple

Re:Night Watchman?

[jollyreaper]

In Soviet Russia they say that because Americans were so poor mathematicians, they had to invent the computer... Or because they Russians were so bad at computer engineering, they had to get good at math instead?

I kid, I kid! But there's good and bad in the American and Russian approaches.