Une équipe de six chercheurs a produit une nouvelle démonstration assistée par ordinateur du théorème des quatre couleurs, selon lequel toute carte connexe peut être coloriée avec quatre couleurs de sorte que les régions voisines soient de couleurs différentes. La démonstration a été mise en ligne en mars 2026 et doit être présentée la semaine prochaine à la conférence annuelle Foundations of Computer Science, à New York.
Ces travaux s’appuient sur un problème qui met les mathématiciens au défi depuis le XIXe siècle. Une première démonstration, annoncée par Alfred Bray Kempe en 1879, s’est révélée erronée 11 ans plus tard. Le théorème a finalement été démontré en 1976 par Kenneth Appel et Wolfgang Haken, qui ont utilisé un ordinateur pour vérifier un grand ensemble de configurations de graphes. Une démonstration ultérieure assistée par ordinateur, publiée en 1997, a réduit le nombre de configurations à vérifier.
La dernière équipe réunit les théoriciens des graphes Carsten Thomassen, Mikkel Thorup, Ken-ichi Kawarabayashi et Bojan Mohar, ainsi que les chercheurs Yuta Inoue et Atsuyuki Miyashita. Leur approche repère un ensemble de 8 202 configurations dans les graphes planaires et permet d’en réduire un grand nombre en parallèle. Les chercheurs affirment que cette méthode rend le processus de coloration nettement plus efficace que la précédente, qui nécessitait un nombre d’étapes augmentant de façon quadratique avec le nombre de sommets du graphe.
Au lieu de se concentrer uniquement sur les zones comprenant des groupes de sommets ayant peu de connexions, l’équipe a étudié les parties plus plates d’un graphe, où les sommets sont reliés selon des arrangements triangulaires. Ces travaux ont également fourni de nouveaux outils pour étudier les propriétés structurelles des graphes planaires, avec des applications potentielles aux problèmes de coloration sur d’autres surfaces, notamment un tore.
La nouvelle démonstration ne répond pas au souhait de longue date de certains mathématiciens de disposer d’une explication plus courte, sans ordinateur, montrant pourquoi quatre couleurs suffisent. Thomassen a déclaré qu’il aimerait voir une démonstration qui ne repose pas sur un ordinateur et qu’il comptait continuer à réfléchir à la question.
Sources: Smithsonian Magazine.