QUATRO CORES PARA QUALQUER MAPA, ENCONTRADAS EM TEMPO LINEAR

Qualquer mapa desenhado numa folha plana pode ser colorido com quatro cores de modo que países vizinhos nunca tenham a mesma. Francis Guthrie conjecturou isso em 1852; Appel e Haken o provaram em 1976. Mas o teorema diz apenas que quatro cores existem. Como encontrá-las para um mapa dado? “Não há resposta fácil”, escrevem Yuta Inoue, da Universidade de Tóquio, e cinco colegas do Japão, do Canadá, da Eslovênia e da Dinamarca. A questão tem sido tão emaranhada que gerou muitos supostos contraexemplos.

Pontos, linhas e triângulos

Cada país vira um ponto, ou vértice, e cada fronteira compartilhada, uma linha, ou aresta: o mapa se torna um grafo planar, desenhado sem linhas que se cruzem. Colori-lo significa dar a cada vértice uma de quatro cores, diferentes nas duas pontas de cada aresta. Chame de n o número de vértices. Basta tratar as triangulações, em que toda face é um triângulo: mais arestas só tornam a coloração mais difícil.

A troca de Kempe

O movimento básico remonta a um artigo de 1879 de A. B. Kempe. Agrupe as quatro cores em pares, digamos vermelho com azul e verde com amarelo. Uma cadeia de Kempe é um grupo conexo de vértices que usam as duas cores de um par. Trocar essas duas cores ao longo de uma cadeia inteira mantém a coloração válida.

Tome um vértice v com quatro vizinhos, de v0 a v3 em ordem ao seu redor, e colora primeiro o resto. Se os vizinhos usam três cores ou menos, v fica com a livre. Se usam as quatro, siga a cadeia que parte de v0 nas cores de v0 e v2. Se ela não chega a v2, troque-a: v0 assume a cor de v2, liberando uma para v. Se ela chega a v2, troque em vez disso a cadeia de v1 nas cores de v1 e v3, para que v1 assuma a cor de v3.

Peças que sempre podem ser consertadas

As provas do teorema se apoiam em configurações redutíveis: pequenos padrões que podem ser recortados e depois recolocados quando o resto estiver colorido. Se as cores de seu anel — os vértices logo em volta deles — não se encaixam, um número limitado de trocas de Kempe de melhoria feitas fora sempre as conserta: no máximo 25 para os padrões usados aqui, cujos anéis têm no máximo 18 vértices.

Uma configuração redutível (à esquerda; cada número é quantos vizinhos esse vértice deve ter no mapa completo) e o mesmo padrão completado por seu anel R (à direita). — Figura 1, Inoue et al. (2026), arXiv:2610.39753.

Robertson, Sanders, Seymour e Thomas mostraram em 1997 como colorir dessa forma, um padrão de cada vez. Cada rodada reduz o grafo em alguns vértices e custa uma passada por ele inteiro, de modo que o tempo é quadrático: quatro vezes mais longo para um mapa duas vezes maior.

Num artigo anterior (FOCS’26), os mesmos seis autores provaram que toda triangulação contém um número de configurações redutíveis que não se tocam proporcional a n, tiradas de uma lista de 8.202 — ou o mesmo número de laços curtos com vértices dos dois lados, que também ajudam. Eles removem todos os padrões de uma vez, colorem o resto e depois consertam todos os anéis juntos. Uma troca de Kempe aleatória ajuda um dado anel se escolher o emparelhamento certo de cores (uma chance em três) e o cara ou coroa certo em cada cadeia que toca o anel (uma chance em duas cada). Com até 18 dessas cadeias, isso dá pelo menos uma chance em 3 × 2¹⁸, ou 786.432: pequena, mas fixa. Assim, o número de rodadas cresce apenas como log n, aproximadamente o número de vezes que n pode ser dividido por dois. Mas uma única troca pode envolver uma fração constante do grafo: cada uma custa uma passada completa, n log n no total.

Uma tabela em vez de uma passada

O novo artigo mantém as log n trocas, mas torna cada uma mais barata. Após uma preparação que leva um tempo proporcional a n, cada troca é encontrada e executada em cerca de n / log n passos, em média. As log n trocas juntas levam então um tempo proporcional a n — tempo linear —, um limite que os autores dizem ser ótimo.

O truque é o “Método dos Quatro Russos” (Method of Four Russians). Um subproblema que cabe num código de ½ log n bits — metade dos dígitos binários necessários para escrever n — tem no máximo √n versões possíveis, de modo que todas as suas respostas podem ser calculadas de antemão e guardadas numa tabela. O computador suposto, com palavras de memória de cerca de log n bits, lê qualquer resposta guardada num único passo.

O grafo é cortado, repetidas vezes, em regiões aninhadas de fronteiras curtas. As menores contêm cerca de log n vértices e cabem, cores incluídas, num único código. Para cada região, um pequeno grafo-resumo registra quais vértices da fronteira compartilham uma cadeia de Kempe. Uma troca então desce como sequências de bits “trocar” ou “manter”, e em cada pequena região uma única consulta atualiza todas as cores.

Parte de um grafo colorido com quatro cores. A área cinza é uma região R; as arestas pretas grossas pertencem às cadeias de Kempe dos pares vermelho-azul e verde-amarelo. — Figura 2, Inoue et al. (2026), arXiv:2610.39753.

O resumo da mesma região: cada mancha azul representa um pedaço de cadeia de Kempe, e suas linhas mostram quais vértices da fronteira ela conecta. — Figura 3, Inoue et al. (2026), arXiv:2610.39753.

Escolher sem dados

Com escolhas aleatórias, isso já colore um mapa em tempo linear, em média. Eliminar os dados sem perder velocidade foi “de longe a parte mais desafiadora”. Diga-se que um anel está vivo enquanto todas as decisões até então lhe foram favoráveis. Se as u cadeias ainda não decididas que o tocam fossem deixadas ao cara ou coroa, ele sobreviveria com probabilidade 1/2^u; somados sobre todos os anéis vivos, esses números dão o número esperado de sobreviventes. Decidir uma cadeia dobra o termo de cada anel que queria aquela escolha e zera os demais. O algoritmo fica com a opção que impede a soma de cair, de modo que, no fim, pelo menos tantos anéis sejam ajudados quanto o acaso teria ajudado em média.

Um limite, não um cronômetro

O artigo não relata nenhuma implementação nem tempo de execução, e as constantes escondidas em “proporcional a n” não são dadas. Elas são grandes: para cada um dos 8.202 padrões, o algoritmo guarda quantas trocas de melhoria cada coloração de seu anel exige — “uma quantidade constante enorme de informação”. Num apêndice, os autores também corrigem “um pequeno erro” numa construção de regiões aninhadas de 2013 na qual se apoiam. Uma conjectura de 1852 vem agora acompanhada de um procedimento de coloração cujo custo não cresce mais rápido do que o mapa que ele colore.