Cómo colorear el mapa de EE. UU. Con amarillo, verde, rojo y azul para minimizar el número de estados con el color verde

Question

Quiero de color de los estados unidos (sólo los estados) mapa de color Amarillo, Verde, Rojo y Azul. Me preguntaba cuál sería el número más bajo de los estados con el color Verde. Por supuesto podemos usar el resto de colores tanto como quieras. Por favor, tenga en cuenta que quiero seguir el Teorema de los Cuatro Colores de las reglas.

Motivación: Estoy estudiando la teoría de grafos y quiero saber si hay una manera de que podamos limitar el uso de la cuarta de color tanto como sea posible. Esta no es una tarea problema.

Mi intento: He intentado muchas variaciones y puede limitar a los 6 y parece que la mínimo posible, pero hay muchas posibilidades para tratar de ($4^{50}$). Por lo tanto, me preguntaba si hay un método más sencillo? Gracias de antemano.

Aclaración: Estoy interesado en sólo la parte continental de Estados Unidos. En estados como Michigan en que se dividen, he utilizado el mismo color por ambas partes (ya que no estaban conectados directamente).

Answer 1

El mínimo es de dos estados que utilizan el cuarto color. Nevada y sus cinco vecinos no puede ser coloreado con sólo tres colores, y de manera similar, West Virginia y sus cinco vecinos no puede ser coloreado con sólo tres colores. En ambos casos, una vez que el color en el centro del estado de un color (por ejemplo, rojo), no se puede utilizar de nuevo en sus vecinos: sin usar de color verde, que tendría que alternar amarillo-azul-amarillo-azul, pero debido a que el número de vecinos es extraña, había de quedar atascado en el final.

(En los comentarios, David K señala que, Kentucky, es un tercer estado con el mismo problema: tiene siete vecinos. Pero esto no nos obliga a usar un tercer estado verde, porque Kentucky y West Virginia, comparten una frontera y algunas común de los vecinos.)

El uso de sólo dos verdes de los estados es posible. Si tenemos en color de Arizona (que se ocupa de la Nevada de la situación) y Ohio (que se ocupa de West Virginia y Kentucky), ambos de color verde, entonces el resto del mapa puede ser completado usando sólo el azul, rojo y amarillo:

Adyacencias entre los estados puede ser más fácil ver aquí.