UMA IA DERRUBA UMA CONJECTURA DE COLORAÇÃO DOS ANOS 1990
Pegue uma rede de pontos ligados por linhas — um grafo. Uma coloração total dá uma cor a cada ponto e a cada linha, seguindo três regras: dois pontos vizinhos diferem, duas linhas que se encontram num ponto diferem, e uma linha difere de seus dois pontos extremos. O menor número de cores que funciona é chamado de número cromático total, escrito χ″(G).
Agora torne o problema mais difícil. Dê a cada ponto e a cada linha sua própria lista de cores permitidas, todas as listas do mesmo tamanho k, e exija uma coloração válida escolhida a partir das listas. O menor k que funciona quaisquer que sejam as listas é o número cromático total por listas, χ″ℓ(G). Ele nunca pode ser menor que χ″(G): se todas as listas forem idênticas, volta-se ao problema comum.
Uma conjectura do fim dos anos 1990
Três grupos — Borodin, Kostochka e Woodall; Juvan, Mohar e Škrekovski; Hilton e Johnson — propuseram de forma independente, no fim dos anos 1990, que listas pessoais nunca custam nada:
χ″ℓ(G) = χ″(G) para todo grafo (mesmo com várias linhas entre dois pontos).
Essa é a Conjectura da Coloração Total por Listas. As evidências a apoiavam: ela vale para grafos em que nenhum ponto tem mais de duas linhas, e sabia-se que todo grafo com exatamente três linhas por ponto (um grafo cúbico) precisava de no máximo 5 cores a partir de listas.
O contraexemplo
Jonathan Noel, da Universidade de Victoria, no Canadá, apresenta agora um grafo cúbico com 20 pontos que tem χ″ = 4, mas χ″ℓ = 5. A conjectura é falsa.
A construção é compacta. Tome quatro cópias de um pequeno grafo chamado K₂,₃: dois pontos “privados”, cada um ligado aos mesmos três pontos “terminais”. Depois, ligue cada par de cópias por exatamente uma linha “cruzada” entre terminais. Cada ponto termina com três linhas.
O grafo G com uma coloração total em apenas quatro cores, indicadas por formas e estilos de linha. — Figura 1, Noel (2026), arXiv:2609.38417.
Quatro cores bastam no jogo comum: a cor 4 vai para todos os pontos privados e todas as linhas cruzadas, que nunca se tocam, e uma pequena tabela e uma regra cíclica cuidam do resto.
Listas impossíveis de satisfazer
A armadilha usa cores de 1 a 5. Cada ponto e cada linha do bloco i recebe a lista “todas as cores exceto i”; as linhas cruzadas recebem listas escolhidas com cuidado, às quais falta 5 ou i + 2. A prova então se desenrola como uma curta história de detetive:
- Lema: em qualquer 4-coloração de K₂,₃, os dois pontos privados devem ter a mesma cor.
- Assim, cada bloco i tem um par de cores {i, sᵢ}, e cada linha cruzada entre dois blocos deve usar uma cor comum aos dois pares.
- Uma pequena contagem mostra que uma cor t deve pertencer aos quatro pares.
- Para cada t possível, uma linha cruzada específica descobre que essa cor falta em sua lista. Contradição.
A atribuição de listas: cada ponto e cada linha pode usar todas as cores de 1 a 5, exceto a indicada. Nenhuma coloração total consegue respeitar essas listas. — Figura 2, Noel (2026), arXiv:2609.38417.
Encontrado por uma máquina, verificado por um matemático
O artigo é invulgarmente franco sobre sua origem. Em 24 de setembro de 2026, Noel pediu ao ChatGPT 6 Astra Ultra que refutasse a conjectura, e ele produziu o contraexemplo, “com pouca contribuição do autor”. Noel verificou os argumentos e reescreveu o texto a partir de rascunhos gerados pelo modelo; o modelo também ajudou na revisão, sugeriu referências e desenhou as figuras. “O autor assume total responsabilidade pela correção”, conclui a declaração. O artigo é um preprint, mas a prova é curta o bastante para que qualquer leitor com paciência a verifique.
Uma diferença de um, ou mais?
Listas pessoais podem custar uma cor a mais. Podem custar mais do que isso? Uma diferença de três também derrubaria uma parente bem estudada, a Conjectura da Coloração de Arestas por Listas, porque χ″ℓ ≤ χ′ℓ + 2 e χ″ ≥ χ′. Noel encerra com uma questão em aberto que o contraexemplo da IA deixa de pé: será que χ″ℓ(G) ≤ χ″(G) + 1 para todo grafo?