CUATRO COLORES PARA CUALQUIER MAPA, HALLADOS EN TIEMPO LINEAL

Cualquier mapa dibujado en una hoja plana puede colorearse con cuatro colores de modo que dos países vecinos nunca compartan uno. Francis Guthrie lo conjeturó en 1852; Appel y Haken lo demostraron en 1976. Pero el teorema solo dice que esos cuatro colores existen. ¿Cómo se encuentran para un mapa concreto? «No hay una respuesta sencilla», escriben Yuta Inoue, de la Universidad de Tokio, y cinco colegas de Japón, Canadá, Eslovenia y Dinamarca. La cuestión ha sido tan enrevesada que dio lugar a muchos supuestos contraejemplos.

Puntos, líneas y triángulos

Cada país se convierte en un punto, o vértice, y cada frontera compartida en una línea, o arista: el mapa se convierte en un grafo plano, dibujado sin líneas que se crucen. Colorearlo significa asignar a cada vértice uno de cuatro colores, distintos en los dos extremos de cada arista. Llamemos n al número de vértices. Basta con tratar las triangulaciones, en las que cada cara es un triángulo: más aristas solo hacen más difícil colorear.

El intercambio de Kempe

El movimiento básico se remonta a un artículo de 1879 de A. B. Kempe. Se emparejan los cuatro colores, por ejemplo rojo con azul y verde con amarillo. Una cadena de Kempe es un grupo conexo de vértices que llevan los dos colores de una pareja. Intercambiar esos dos colores a lo largo de toda una cadena mantiene válida la coloración.

Tomemos un vértice v con cuatro vecinos, de v0 a v3 en orden a su alrededor, y coloreemos primero el resto. Si los vecinos usan tres colores o menos, v toma el que queda libre. Si usan los cuatro, se sigue la cadena que parte de v0 con los colores de v0 y v2. Si no llega a v2, se intercambia: v0 toma el color de v2 y deja uno libre para v. Si llega a v2, se intercambia en su lugar la cadena de v1 con los colores de v1 y v3, de modo que v1 tome el color de v3.

Piezas que siempre pueden repararse

Las demostraciones del teorema se basan en configuraciones reducibles: pequeños patrones que se pueden recortar y volver a colocar una vez coloreado el resto. Si los colores de su anillo —los vértices que los rodean directamente— no encajan, un número acotado de cambios de Kempe de mejora hechos fuera siempre los arregla: como máximo 25 para los patrones usados aquí, cuyos anillos tienen como mucho 18 vértices.

Una configuración reducible (izquierda; cada número indica cuántos vecinos debe tener ese vértice en el mapa completo) y el mismo patrón completado por su anillo R (derecha). — Figura 1, Inoue et al. (2026), arXiv:2610.39753.

Robertson, Sanders, Seymour y Thomas mostraron en 1997 cómo colorear de este modo, un patrón cada vez. Cada ronda reduce el grafo en unos pocos vértices y cuesta una pasada por todo él, así que el tiempo es cuadrático: cuatro veces más largo para un mapa el doble de grande.

En un artículo anterior (FOCS’26), los mismos seis autores demostraron que toda triangulación contiene un número de configuraciones reducibles que no se tocan proporcional a n, tomadas de una lista de 8.202, o bien otros tantos bucles cortos con vértices a ambos lados, que también sirven. Eliminan todos los patrones a la vez, colorean el resto y luego reparan todos los anillos juntos. Un cambio de Kempe aleatorio ayuda a un anillo dado si elige el emparejamiento de colores adecuado (una posibilidad entre tres) y si sale la moneda adecuada en cada cadena que toca el anillo (una posibilidad entre dos por cadena). Con hasta 18 cadenas así, eso supone al menos una posibilidad entre 3 × 2¹⁸, es decir, 786.432: pequeña, pero fija. Así que el número de rondas solo crece como log n, aproximadamente el número de veces que puede dividirse n por la mitad. Pero un solo cambio puede afectar a una fracción constante del grafo: cada uno cuesta una pasada completa, n log n en total.

Una tabla en vez de una pasada

El nuevo artículo mantiene los log n cambios, pero abarata cada uno. Tras una preparación que lleva un tiempo proporcional a n, cada cambio se encuentra y se ejecuta en unos n / log n pasos de media. Los log n cambios juntos llevan entonces un tiempo proporcional a n —tiempo lineal—, una cota que los autores califican de óptima.

El truco es el «método de los cuatro rusos» (Method of Four Russians). Un subproblema que cabe en un código de ½ log n bits —la mitad de las cifras binarias necesarias para escribir n— tiene como mucho √n versiones posibles, así que todas sus respuestas pueden calcularse de antemano y guardarse en una tabla. El ordenador supuesto, con palabras de memoria de unos log n bits, lee cualquier respuesta guardada en un solo paso.

El grafo se corta, una y otra vez, en regiones anidadas con fronteras cortas. Las más pequeñas contienen unos log n vértices y caben, colores incluidos, en un solo código. Para cada región, un pequeño grafo resumen registra qué vértices de la frontera comparten una cadena de Kempe. Un cambio desciende entonces como cadenas de bits de «intercambiar» o «mantener», y en cada región pequeña una sola consulta actualiza todos los colores.

Parte de un grafo coloreado con cuatro colores. La zona gris es una región R; las aristas negras gruesas pertenecen a las cadenas de Kempe de las parejas rojo-azul y verde-amarillo. — Figura 2, Inoue et al. (2026), arXiv:2610.39753.

El resumen de la misma región: cada mancha azul representa un trozo de cadena de Kempe, y sus líneas muestran qué vértices de la frontera conecta. — Figura 3, Inoue et al. (2026), arXiv:2610.39753.

Elegir sin dados

Con elecciones aleatorias, esto ya colorea un mapa en tiempo lineal de media. Quitar los dados sin perder velocidad fue «con diferencia la parte más difícil». Digamos que un anillo está vivo mientras todas las decisiones tomadas hasta el momento le hayan sido favorables. Si las u cadenas aún no decididas que lo tocan se dejaran a cara o cruz, sobreviviría con probabilidad 1/2^u; sumados sobre todos los anillos vivos, estos números dan el número esperado de supervivientes. Decidir una cadena duplica el término de cada anillo que quería esa elección y anula los demás. El algoritmo toma la opción que impide que la suma baje, de modo que al final se ayuda al menos a tantos anillos como el azar habría ayudado de media.

Una cota, no un cronómetro

El artículo no presenta ninguna implementación ni ningún tiempo de ejecución, y las constantes ocultas en «proporcional a n» no se dan. Son grandes: para cada uno de los 8.202 patrones, el algoritmo guarda cuántos cambios de mejora necesita cada coloración de su anillo, «una enorme cantidad constante de información». En un apéndice, corrigen además «un error menor» en una construcción de regiones anidadas de 2013 en la que se apoyan. Una conjetura de 1852 viene ahora acompañada de un procedimiento de coloreado cuyo coste no crece más deprisa que el mapa que colorea.