Quatre couleurs suffisent pour colorier toute carte, sans deux voisins de même couleur. C'est démontré depuis 1976. Mais comment trouver ces couleurs, concrètement ?
L'outil classique est la chaîne de Kempe. Prenez deux couleurs et tout le bloc d'un seul tenant de pays peints de ces deux couleurs. Échangez-les dans tout le bloc : la carte reste bien coloriée.
Le hic : un seul échange peut se propager à toute la carte. Le record précédent demandait plus d'échanges à mesure que les cartes grandissaient. Chacun coûtait un passage complet sur la carte.
Six mathématiciens, de Tokyo à Copenhague, ont supprimé ce surcoût. Leur algorithme colorie n pays en un temps proportionnel à n. Les petits morceaux de carte sont résolus une fois, rangés en tables, puis consultés. Les auteurs jugent cette vitesse optimale.
Source : Four-Coloring Planar Graphs in Linear Time, https://arxiv.org/abs/2610.39753










