Coloración en gráficas de mapas en la tierra y mapas en la luna.


== 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.


== Document ==
<pdf>Media:Draft_Calderon Juarez_591692200-2681-document.pdf</pdf>