Aspect historique
C’est au XIXème siècle que la théorie de la coloration de graphes a pour la première fois été évoquée. On s’interrogeait alors sur des problèmes de coloration de cartes géographiques. En 1852, Francis Guthrie (1831-1899, mathématicien sud-africain), énonça une conjecture, appelée le « problème des quatre couleurs ». Cette conjecture est la suivante : il est possible de colorer les sommets d’un graphe planaire en utilisant au plus quatre couleurs de telle sorte que toutes les arêtes aient des extrémités de couleurs différentes.
Pendant plus d’un siècle, plusieurs mathématiciens, dont A. De Morgan et W.R. Hamilton, tentèrent de résoudre ce problème, en vain. En 1879 et 1880, A. Kempe et P. Guthrie, publièrent deux démonstrations. Celles-ci furent démontées en 1890 par P. Heawood.
Ce n’est qu’en 1976, que Kenneth Appel et Wolfgang Haken, réussirent à démontrer le théorème. Ce théorème est aussi le premier problème mathématique démontré grâce à un ordinateur.
Sources:
cours-info.iut-bm.univ-fcomte.fr
researchgate.net/Graph_Coloring_History_results_and_open_problems
Inscrivez-vous au blog
Soyez prévenu par email des prochaines mises à jour
Rejoignez les 4 autres membres