QUATRE COULEURS PROBLÈME DES

Position du problème

On veut colorier une carte géographique tracée sur le plan (ou la sphère) de manière que deux régions voisines soient toujours de couleurs différentes. Précisons que chaque région est connexe (d'un seul tenant) et que deux régions voisines ont au moins une ligne frontière en commun. Dans ces conditions, les cartographes ont constaté que toute carte pouvait être coloriée avec quatre couleurs au plus. C'est cette proposition, appelée conjecture des quatre couleurs, qui a été démontrée par Kenneth Appel et Wolfgang Haken.

Dans les travaux récents, on préfère considérer le graphe dual de la carte, qu'on obtient en choisissant dans chaque région un point intérieur (son chef-lieu) et en reliant par une courbe simple (arête) les chefs-lieux de deux régions voisines. Ce graphe peut être tracé sur le plan sans que deux arêtes se coupent (graphe planaire topologique) ; par nature, il ne comporte pas de boucles. Ce sont les chefs-lieux que l'on colorie. La proposition s'énonce alors :

Les sommets d'un graphe planaire sans boucles peuvent être coloriés avec quatre couleurs de manière que toute arête ait ses extrémités de couleurs différentes.

1  2  3  4  5 …
pour nos abonnés,
l’article se compose de 4 pages

Médias de l’article

Réduction d'une configuration v4 d'un graphe planaire triangulé
Crédits : Encyclopædia Universalis France

dessin

Réductibilité d'un quadrilatère
Crédits : Encyclopædia Universalis France

dessin

Afficher les 2 médias de l'article