En teoría de grafos el teorema de coloreo de carreteras, teorema del camino coloreado o, conocido antiguamente como la conjetura del coloreo de carreteras, es un problema de coloreo de grafos planos. El planteamiento inicial, en términos intuitivos, consiste en que dada una red (grafo que representa ya sea una ciudad o laberinto) con determinadas condiciones, y dada una posición en el mismo, buscar si existe, y cuál es, una serie de instrucciones que independientemente del posicionamiento inicial, permitan llegar a la posición requerida.[1]​
Usualmente, este problema se plantea en términos coloquiales como:

 

Este teorema fue conjeturado por primera vez por Roy Adler, Wayne Goodwyn y Benjamin Weiss en 1970[2]​ y replanteado en 1977,[3]​ siendo probado 37 años después, en 2007 por el israelí de origen ruso Avraham Trahtman.[4]​[5]​ Sus aplicaciones van desde la cartografía hasta el simbolismo dinámico y la teoría de automatización.[6]​