Abstract

La ''coloración de mapas'' es un problema clásico en la ''Teoría de Grafos'', donde cada país se modela como un vértice y las fronteras entre países como aristas. El ''Teorema de los Cuatro Colores'' establece que cualquier mapa plano puede colorearse con cuatro colores sin que dos regiones adyacentes compartan el mismo color. En este artículo, exploramos la generalización del problema de coloración de mapas al caso de la Tierra y la Luna, conocido como el '''Earth Moon Problem''', propuesto por Ringel. Este problema busca determinar el número mínimo de colores necesarios para colorear un mapa donde cada país en la Tierra y su colonia lunar deben recibir el mismo color, respetando la restricción de que las regiones adyacentes en cualquiera de los dos cuerpos celestes deben tener colores distintos. Nuestro principal aporte es demostrar que el problema de la ''3-coloración'' de la Tierra-Luna es ''NP-completo'', mediante una reducción desde ''3-SAT'', lo que implica que no existe un algoritmo eficiente para resolverlo en general (suponiendo P ≠ NP). Además, complementamos demostraciones previas que aparecían incompletas en la literatura y modelamos el problema como un ''problema de satisfacción de restricciones'' (CSP), lo que permite un análisis más profundo de su complejidad computacional. Este trabajo no solo aporta una nueva demostración de que el problema de coloración de la Tierra-Luna con 3 colores es NP-completo, sino que también abre la puerta a futuros estudios sobre su dificultad para diferentes números de colores. Por último, describir el problema de coloración de la Tierra-Luna a través de grafos, un caso abierto en la coloración de grafos que extiende el problema de la coloración de mapas planos. En términos de grafos, esto se puede reformular como la búsqueda del '''número cromático máximo''' de un grafo G que es la unión de dos grafos planares (sobre el mismo conjunto de vértices). Se demuestra mediante inducción que G es 12-coloreable, como observó Heawood. Ringel conjeturó que el Problema de la Tierra-Luna era 8-coloreable pero Sulanke reportó un ejemplo que requiere 9 colores, aún no se conoce si existen configuraciones que requieran 10, 11 o 12 colores.