QUATRE COULEURS POUR TOUTE CARTE, TROUVÉES EN TEMPS LINÉAIRE

Toute carte dessinée sur une feuille plane peut être coloriée avec quatre couleurs de sorte que deux pays voisins n’aient jamais la même. Francis Guthrie l’a conjecturé en 1852 ; Appel et Haken l’ont démontré en 1976. Mais le théorème dit seulement que les quatre couleurs existent. Comment les trouver pour une carte donnée ? « Il n’y a pas de réponse simple », écrivent Yuta Inoue, de l’université de Tokyo, et cinq collègues du Japon, du Canada, de Slovénie et du Danemark. La question a été si embrouillée qu’elle a conduit à de nombreux prétendus contre-exemples : des cartes pour lesquelles personne ne trouvait quatre couleurs.

Des points, des traits et des triangles

Chaque pays devient un point, ou sommet, et chaque frontière commune un trait, ou arête : la carte devient un graphe planaire, dessiné sans qu’aucun trait n’en croise un autre. Le colorier, c’est donner à chaque sommet l’une des quatre couleurs, différente aux deux bouts de chaque arête. Notons n le nombre de sommets. Il suffit de traiter les triangulations, où chaque face — chaque zone délimitée par des arêtes — est un triangle : ajouter des arêtes ne peut que compliquer le coloriage.

L’échange de Kempe

Le geste de base remonte à un article de 1879 d’A. B. Kempe. Associez les quatre couleurs par paires, par exemple rouge avec bleu et vert avec jaune. Une chaîne de Kempe est un groupe connexe de sommets qui portent les deux couleurs d’une même paire. Échanger ces deux couleurs sur toute une chaîne laisse le coloriage valide.

Prenez un sommet v à quatre voisins, v0 à v3 dans l’ordre autour de lui, et coloriez d’abord le reste. Si les voisins utilisent trois couleurs ou moins, v prend celle qui reste libre. S’ils utilisent les quatre, suivez la chaîne qui part de v0 dans les couleurs de v0 et de v2. Si elle n’atteint pas v2, échangez-la : v0 prend la couleur de v2, ce qui en libère une pour v. Si elle atteint v2, échangez plutôt la chaîne de v1 dans les couleurs de v1 et de v3, pour que v1 prenne la couleur de v3. Cette seconde chaîne ne peut pas atteindre v3 : la première, de v0 à v2 et refermée par v, forme une boucle qui isole v1 de v3. C’est là que sert le fait que la carte soit plane.

Des morceaux toujours réparables

Les preuves du théorème reposent sur des configurations réductibles : de petits motifs que l’on peut découper, puis remettre une fois le reste colorié. Si les couleurs de leur anneau — les sommets qui les entourent directement — ne conviennent pas, un nombre borné d’échanges de Kempe améliorants — chacun rapproche d’un cran les couleurs de l’anneau d’un coloriage qui convient —, faits à l’extérieur, les corrige toujours : au plus 25 pour les motifs utilisés ici, dont les anneaux ont au plus 18 sommets.

Une configuration réductible (à gauche ; chaque nombre indique combien de voisins ce sommet doit avoir dans la carte complète) et le même motif complété par son anneau R (à droite). — Figure 1, Inoue et al. (2026), arXiv:2610.39753.

Robertson, Sanders, Seymour et Thomas ont montré en 1997 comment colorier ainsi, un motif à la fois. Chaque tour réduit le graphe de quelques sommets et coûte un passage sur tout le graphe : le temps est donc quadratique, quatre fois plus long pour une carte deux fois plus grande.

Dans un article précédent (FOCS’26), les six mêmes auteurs ont prouvé que toute triangulation contient un nombre proportionnel à n de configurations réductibles sans contact entre elles, tirées d’une liste de 8 202 — ou autant de petites boucles ayant des sommets des deux côtés, qui servent aussi. Ils retirent tous les motifs d’un coup, colorient le reste, puis réparent tous les anneaux ensemble. Un échange de Kempe tiré au hasard aide un anneau donné s’il tombe sur le bon appariement des couleurs (une chance sur trois) et sur le bon pile ou face pour chaque chaîne qui touche l’anneau (une chance sur deux chacune). Avec jusqu’à 18 chaînes, cela fait au moins une chance sur 3 × 2¹⁸, soit 786 432 : peu, mais une valeur fixe. Chaque série d’échanges aide donc une part fixe des anneaux encore en attente, et un anneau en demande au plus 25 : le nombre d’anneaux non réparés baisse d’un facteur fixe à chaque fois. Le nombre de tours ne croît donc que comme log n, à peu près le nombre de fois qu’on peut diviser n par deux. Mais un seul échange peut toucher une part fixe du graphe entier, quelle que soit sa taille : chacun coûte un passage complet, soit n log n au total.

Une table plutôt qu’un passage

Le nouvel article garde les log n échanges, mais rend chacun moins cher. Après une préparation qui prend un temps proportionnel à n, chaque échange est trouvé et effectué en environ n / log n étapes par échange, en moyenne sur l’ensemble des échanges. Les log n échanges prennent alors ensemble un temps proportionnel à n — un temps linéaire —, une borne que les auteurs jugent optimale.

L’astuce est la « méthode des Quatre Russes ». Un sous-problème qui tient dans un code de ½ log n bits — la moitié des chiffres binaires qu’il faut pour écrire n — a au plus √n versions possibles : toutes leurs réponses peuvent être calculées d’avance et rangées dans une table. L’ordinateur supposé, avec des mots mémoire d’environ log n bits, lit n’importe quelle réponse rangée en une seule étape.

Le graphe est découpé, encore et encore, en régions emboîtées aux bords courts. Les plus petites contiennent environ log n sommets et tiennent, couleurs comprises, dans un seul code. Pour chaque région, un petit graphe résumé indique quels sommets du bord appartiennent à la même chaîne de Kempe. Un échange descend alors sous forme de suites de bits « échanger » ou « garder », et dans chaque petite région une seule lecture de table met à jour toutes les couleurs. Avec environ n / log n petites régions, un échange coûte donc environ n / log n lectures.

Partie d’un graphe colorié avec quatre couleurs. La zone grise est une région R ; les arêtes noires épaisses appartiennent aux chaînes de Kempe des paires rouge-bleu et vert-jaune. — Figure 2, Inoue et al. (2026), arXiv:2610.39753.

Le résumé de la même région : chaque tache bleue représente un morceau de chaîne de Kempe, et ses traits montrent quels sommets du bord il relie. — Figure 3, Inoue et al. (2026), arXiv:2610.39753.

Choisir sans les dés

Avec des choix aléatoires, cela colorie déjà une carte en temps linéaire en moyenne. Se passer des dés sans perdre en vitesse a été « de loin la partie la plus difficile ». Disons qu’un anneau est vivant tant que chaque décision prise est allée dans son sens. Si les u chaînes non décidées qui le touchent étaient laissées à pile ou face, il survivrait avec une probabilité de 1/2^u ; additionnés sur tous les anneaux vivants, ces nombres donnent le nombre attendu de survivants. Décider une chaîne double le terme de chaque anneau qui voulait ce choix et annule celui des autres. L’algorithme prend l’option qui empêche la somme de baisser : à la fin, au moins autant d’anneaux sont aidés que le hasard en aurait aidé en moyenne.

Une borne, pas un chronomètre

L’article ne présente aucune implémentation ni aucun temps d’exécution, et les constantes cachées dans « proportionnel à n » ne sont pas données. Elles sont grandes : pour chacun des 8 202 motifs, l’algorithme stocke combien d’échanges améliorants demande chaque coloriage de son anneau — « une énorme quantité constante d’information ». Dans une annexe, les auteurs corrigent aussi « une erreur mineure » dans une construction de régions emboîtées de 2013 sur laquelle ils s’appuient. Une conjecture de 1852 dispose désormais d’une procédure de coloriage dont le coût ne croît pas plus vite que la carte qu’elle colorie.