FR  |  EN  
  ENS sur facebook ENS sur twitter ENS sur youtube ENS sur google+
École normale supérieure
Lien vers la page d'accueil de l'ENS Lien vers l'article de l'ENS
> ACTUALITÉS > Publications > La « conjecture des trois couleurs » de Steinberg invalidée

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.

Mai 2016

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.

Voir l’intégralité de l’article de Sean Bailly sur Pour la Science 17/05/2016

Contacts & Plans  |   L'ENS recrute  |   Marchés publics  |   Annuaire  |   Intranet-ENT  |   Mentions légales  |   Plan du site  |   ENS sur facebook ENS sur twitter ENS sur youtube ENS sur google+