UNE IA FAIT TOMBER UNE CONJECTURE DE COLORIAGE

Prenez un réseau de points reliés par des traits — un graphe. Un coloriage total donne une couleur à chaque point et à chaque trait, selon trois règles : deux points voisins diffèrent, deux traits qui se rejoignent en un point diffèrent, et un trait diffère de ses deux extrémités. Le plus petit nombre de couleurs qui fonctionne s’appelle le nombre chromatique total, noté χ″(G).

Corsons le jeu. Donnons à chaque point et à chaque trait sa propre liste de couleurs autorisées, toutes de même taille k, et exigeons un coloriage valable pioché dans les listes. Le plus petit k qui marche quelles que soient les listes est le nombre chromatique total par listes, χ″ℓ(G). Il ne peut jamais être plus petit que χ″(G) : si toutes les listes sont identiques, on retombe sur le problème ordinaire.

Une conjecture de la fin des années 1990

Trois groupes — Borodin, Kostochka et Woodall ; Juvan, Mohar et Škrekovski ; Hilton et Johnson — ont proposé indépendamment, à la fin des années 1990, que les listes personnelles ne coûtent jamais rien :

χ″ℓ(G) = χ″(G) pour tout graphe (même avec plusieurs traits entre deux points).

C’est la conjecture du coloriage total par listes. Des indices plaidaient pour elle : elle est vraie pour les graphes où aucun point n’a plus de deux traits, et l’on savait que tout graphe à exactement trois traits par point (un graphe cubique) demande au plus 5 couleurs à partir de listes.

Le contre-exemple

Jonathan Noel, de l’université de Victoria au Canada, présente un graphe cubique de 20 points pour lequel χ″ = 4 mais χ″ℓ = 5. La conjecture est fausse.

La construction est compacte. Prenez quatre copies d’un petit graphe appelé K₂,₃ : deux points « privés », reliés chacun aux trois mêmes points « terminaux ». Reliez ensuite chaque paire de copies par un seul trait « croisé » entre terminaux. Chaque point se retrouve avec trois traits.

Le graphe G avec un coloriage total en seulement quatre couleurs, indiquées par les formes et les styles de traits. — Figure 1, Noel (2026), arXiv:2609.38417.

Quatre couleurs suffisent dans le jeu ordinaire : la couleur 4 va à tous les points privés et à tous les traits croisés, qui ne se touchent jamais, et un petit tableau plus une règle cyclique règlent le reste.

Des listes impossibles à satisfaire

Le piège utilise les couleurs 1 à 5. Chaque point et chaque trait du bloc i reçoit la liste « toutes les couleurs sauf i » ; les traits croisés reçoivent des listes soigneusement choisies, privées de 5 ou de i + 2. La preuve se déroule alors comme une courte enquête :

• Lemme : dans tout coloriage de K₂,₃ en 4 couleurs, les deux points privés ont forcément la même couleur.
• Chaque bloc i a donc une paire de couleurs {i, sᵢ}, et chaque trait croisé entre deux blocs doit utiliser une couleur commune aux deux paires.
• Un petit raisonnement de dénombrement montre qu’une couleur t appartient forcément aux quatre paires.
• Pour chaque valeur possible de t, un trait croisé précis ne trouve pas cette couleur dans sa liste. Contradiction.

L’attribution des listes : chaque point et chaque trait peut utiliser toutes les couleurs de 1 à 5 sauf celle indiquée. Aucun coloriage total ne peut respecter ces listes. — Figure 2, Noel (2026), arXiv:2609.38417.

Trouvé par une machine, vérifié par un mathématicien

L’article est d’une franchise inhabituelle sur son origine. Le 24 septembre 2026, Noel a demandé à ChatGPT 6 Astra Ultra de réfuter la conjecture, et le modèle a produit le contre-exemple, « avec peu d’apport de l’auteur ». Il a vérifié les arguments et réécrit le texte à partir de brouillons générés par le modèle ; celui-ci a aussi aidé à la relecture, suggéré des références et dessiné les figures. « L’auteur assume l’entière responsabilité de l’exactitude », conclut la déclaration. L’article est un preprint, mais la preuve est assez courte pour que tout lecteur patient la vérifie.

Un écart d’une couleur, ou plus ?

Les listes personnelles peuvent coûter une couleur de plus. Peuvent-elles en coûter davantage ? Un écart de trois ferait aussi tomber une cousine bien étudiée, la conjecture du coloriage des arêtes par listes, car χ″ℓ ≤ χ′ℓ + 2 et χ″ ≥ χ′. Noel termine sur une question ouverte que le contre-exemple de l’IA laisse debout : a-t-on χ″ℓ(G) ≤ χ″(G) + 1 pour tout graphe ?