Quatro cores bastam para qualquer mapa, de modo que vizinhos sempre tenham cores diferentes. Isso foi provado em 1976. Mas como encontrar as cores na prática?
A ferramenta clássica é a cadeia de Kempe. Escolha duas cores e tome toda a região conexa de países pintados só com elas. Troque-as em toda a região: o mapa continua corretamente colorido.
O problema: uma única troca pode se propagar pelo mapa inteiro. O recorde anterior precisava de mais trocas à medida que os mapas cresciam. Cada uma custava uma passada completa pelo mapa.
Seis matemáticos, de Tóquio a Copenhague, eliminaram esse custo extra. Seu algoritmo colore n países num tempo proporcional a n. Pequenos pedaços do mapa são resolvidos uma vez, guardados em tabelas e depois simplesmente consultados. Os autores dizem que essa velocidade é ótima.
Fonte: Four-Coloring Planar Graphs in Linear Time, https://arxiv.org/abs/2610.39753










