La « conjecture des trois couleurs » de Steinberg invalidée
Un article de Pour la science évoque un résultat récent sur le coloriage de graphes obtenu dans l’équipe Talgo du Département d’informatique de l’ENS.
Il suffit de quatre couleurs pour colorier n’importe quelle carte plane de sorte que deux régions voisines soient de couleurs différentes. La conjecture de Steinberg énonçait certaines conditions pour que trois couleurs suffisent. Mais elle est fausse : un contre-exemple a été trouvé.
Combien de couleurs différentes sont nécessaires pour colorier une carte plane sans que deux pays voisins soient de la même couleur ? En 1976, les Américains Kenneth Appel et Wolfgang Haken ont démontré que quatre couleurs suffisaient quelle que soit la carte.
En revanche, trois couleurs ne suffisent pas en général. On pensait néanmoins que c’était possible pour certains types de cartes. C’est l’objet de la conjecture de Richard Steinberg, énoncée en 1976, selon laquelle « tout graphe planaire sans cycle de longueur 4 ou 5 peut être colorié avec seulement trois couleurs ». Or Vincent Cohen-Addad et Zhentao Li, de l’École normale supérieure de Paris, et leurs collègues Michael Hebdige, Daniel Král’ et Esteban Salgado, alors en visite à l’ENS, viennent de montrer que cette conjecture est fausse en trouvant un contre-exemple.