UNA IA TUMBA UNA CONJETURA DE COLOREO DE LOS AÑOS 90

Tomemos una red de puntos unidos por líneas: un grafo. Un coloreado total asigna un color a cada punto y a cada línea, siguiendo tres reglas: dos puntos vecinos tienen colores distintos, dos líneas que se encuentran en un punto tienen colores distintos, y una línea tiene un color distinto del de sus dos extremos. El menor número de colores con el que esto funciona se llama número cromático total y se escribe χ″(G).

Ahora, compliquémoslo. Demos a cada punto y a cada línea su propia lista de colores permitidos, todas las listas del mismo tamaño k, y exijamos un coloreado válido elegido a partir de las listas. El menor k que funciona sean cuales sean las listas es el número cromático total por listas, χ″ℓ(G). Nunca puede ser menor que χ″(G): si todas las listas son idénticas, se vuelve al problema ordinario.

Una conjetura de finales de los años 90

Tres grupos —Borodin, Kostochka y Woodall; Juvan, Mohar y Škrekovski; Hilton y Johnson— propusieron de forma independiente, a finales de los años 90, que las listas personales nunca cuestan nada:

χ″ℓ(G) = χ″(G) para todo grafo (incluso con varias líneas entre dos puntos).

Es la conjetura del coloreado total por listas (List Total Colouring Conjecture). Los indicios la respaldaban: se cumple para los grafos en los que ningún punto tiene más de dos líneas, y se sabía que todo grafo con exactamente tres líneas por punto (un grafo cúbico) necesita como máximo 5 colores a partir de listas.

El contraejemplo

Jonathan Noel, de la Universidad de Victoria, en Canadá, presenta ahora un grafo cúbico de 20 puntos con χ″ = 4 pero χ″ℓ = 5. La conjetura es falsa.

La construcción es compacta. Se toman cuatro copias de un pequeño grafo llamado K₂,₃: dos puntos «privados», cada uno unido a los mismos tres puntos «terminales». Después se une cada par de copias mediante exactamente una línea «cruzada» entre terminales. Cada punto acaba con tres líneas.

El grafo G con un coloreado total de solo cuatro colores, indicados mediante formas y estilos de línea. — Figura 1, Noel (2026), arXiv:2609.38417.

En el juego ordinario bastan cuatro colores: el color 4 se asigna a todos los puntos privados y a todas las líneas cruzadas, que nunca se tocan entre sí, y una pequeña tabla y una regla cíclica se encargan del resto.

Listas imposibles de satisfacer

La trampa usa los colores del 1 al 5. Cada punto y cada línea del bloque i recibe la lista «todos los colores excepto i»; las líneas cruzadas reciben listas cuidadosamente elegidas a las que les falta el 5 o i + 2. La demostración se desarrolla entonces como una breve novela policiaca:

• Lema: en cualquier coloreado de K₂,₃ con 4 colores, los dos puntos privados deben tener el mismo color.
• Así, cada bloque i tiene un par de colores {i, sᵢ}, y toda línea cruzada entre dos bloques debe usar un color común a ambos pares.
• Un pequeño recuento muestra que un color t debe pertenecer a los cuatro pares.
• Para cada valor posible de t, hay una línea cruzada concreta en cuya lista falta ese color. Contradicción.

La asignación de listas: cada punto y cada línea puede usar cualquier color del 1 al 5 excepto el indicado. Ningún coloreado total puede respetar estas listas. — Figura 2, Noel (2026), arXiv:2609.38417.

Encontrado por una máquina, comprobado por un matemático

El artículo es inusualmente franco sobre su origen. El 24 de septiembre de 2026, Noel pidió a ChatGPT 6 Astra Ultra que refutara la conjetura, y este produjo el contraejemplo, «con poca intervención del autor». Él comprobó los argumentos y reescribió el texto a partir de borradores generados por el modelo; el modelo también ayudó a revisar el texto, sugirió referencias y dibujó las figuras. «El autor asume plena responsabilidad por su corrección», concluye la declaración. El artículo es una prepublicación, pero la demostración es lo bastante breve como para que cualquier lector con paciencia la verifique.

¿Una diferencia de uno, o más?

Las listas personales pueden costar un color extra. ¿Pueden costar más? Una diferencia de tres derribaría también a una pariente muy estudiada, la conjetura del coloreado de aristas por listas (List Edge Colouring Conjecture), porque χ″ℓ ≤ χ′ℓ + 2 y χ″ ≥ χ′. Noel cierra con una pregunta abierta que el contraejemplo de la IA deja en pie: ¿se cumple χ″ℓ(G) ≤ χ″(G) + 1 para todo grafo?