Teorema del coloreo de carreteras

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, éstas permitan llegar a la posición requerida.Usualmente, este problema se plantea en términos coloquiales como:Supongamos que alguien visita una ciudad que no conoce, con la peculiaridad de que dicho lugar no contiene ninguna clase de señal indicativa. Luego de haber vagado un par de horas, el visitante le pide ayuda a alguien para llegar a determinado lugar, contándole que no sabe dónde está. ¿Existe alguna serie de instrucciones que se le puedan dar al turista para que, independientemente de dónde se encuentre, pueda llegar a su destino?Este teorema fue conjeturado por primera vez por Roy Adler, Wayne Goodwyn y Benjamin Weiss en 1970 y replanteado en 1977, siendo probado 37 años después, en 2007 por el israelí de origen ruso Avraham Trahtman. Sus aplicaciones van desde la cartografía hasta el simbolismo dinámico y la teoría de automatización.