road-colouring problem

The road-colouring problem, a variant of the traveling salesman problem, was solved by mathematician Avraham Trahtman in 2007. This problem in graph theory concerns a specific type of network. The network must be finite, strongly connected (meaning a path exists between any two points), and aperiodic. The road-colouring theorem states that for such networks, there's always a synchronized coloring method. This method uses a simple set of directions, possibly with repetitions, to guide a traveler from any starting point to any destination. For example, following a "red-blue-red" path ensures arrival at the intended location. Trahtman's proof was exceptionally concise, spanning less than eight pages.1

This is distinct from the four-colour map problem, which deals with coloring planar maps such that adjacent regions have different colors, and was proven by Kenneth Appel and Wolfgang Haken in 1976.2