Trahtman (2009) solved the road coloring problem by proving that such a coloring can be found whenever the given graph is strongly connected and aperiodic.
(Trahtman 2009) megoldotta az útszínezési problémát azt bebizonyítva, hogy ilyen színezés mindig található, amennyiben a bemeneti gráf erősen összefüggő és aperiodikus.