Cuatro colores bastan para cualquier mapa, de modo que los vecinos siempre sean distintos. Se demostró en 1976. Pero ¿cómo se encuentran de verdad esos colores?
La herramienta clásica es la cadena de Kempe. Se eligen dos colores. Se toma toda la zona conexa de países pintados solo con esos dos. Si se intercambian en toda la zona, el mapa sigue bien coloreado.
El problema: un solo intercambio puede propagarse por todo el mapa. El récord anterior necesitaba más intercambios a medida que crecían los mapas. Cada uno costaba una pasada completa por el mapa.
Seis matemáticos, de Tokio a Copenhague, han eliminado ese coste extra. Su algoritmo colorea n países en un tiempo proporcional a n. Los pedacitos del mapa se resuelven una vez, se guardan en tablas y luego simplemente se consultan. Los autores califican esta velocidad de óptima.
Fuente: Four-Coloring Planar Graphs in Linear Time, https://arxiv.org/abs/2610.39753










