FSE du Collège Joseph-Anglade

En 1852 Francis Guthrie, cartographe anglais, remarque qu’il lui suffit de quatre couleurs pour colorer la carte des cantons d’Angleterre, sans donner la même couleur à deux cantons adjacents. Il demande donc à son frère Frederick, mathématicien, si cette propriété ne serait pas vraie en général pour toute carte plane ; celui-ci communique la conjecture à De Morgan, et en 1878 Cayley la publie.

En 1879, Kempe trouve une première preuve de la conjecture, mais onze ans plus tard Heawood y trouvera une faille majeure ; il parviendra toutefois à en sauver un théorème des cinq couleurs. Une seconde preuve par Tait en 1880 sera de même réfutée par Petersen en 1891.

En 1913, le père de l’algèbre moderne, G. D. Birkhoff démontre la conjecture pour toutes les cartes comportant moins de 26 régions à colorier. Cette borne est améliorée au cours du XX^e siècle ; en 1969 Heesch trouve des conditions presque nécessaires et suffisantes pour qu’une configuration soit réductible, et une méthode générale pour trouver un ensemble inévitable de configurations.

Finalement, en 1976, Appel et Haken réalisent le programme de Heesch, et montrent, dizaines de milliers de figures à l’appui, que toute carte non 4-coloriable doit contenir l’une de 1 478 configurations, et, avec 1 200 heures de calcul, que chacune de ces configurations sont réductibles.

Enfin, en 1995, Robertson, Sanders, Seymour et Thomas mettent à profit la formidable accélération des ordinateurs pour trouver une réalisation nettement plus simple du programme de Heesch, avec seulement 633 configurations.

[youtube]https://www.youtube.com/watch?v=g_nTfZ9OgJs[/youtube]