4. Coloriage : théorème des quatre couleurs et théorème des graphes parfaits
Quand on commence par jouer avec des crayons de couleur, on finit parfois par faire de l'algèbre de bords et de cobords ! Les théoriciens des graphes, amateurs de petits dessins, ne pouvaient manquer de chercher à les colorier ! Mais sous ces dessins multicolores se cachent de jolis problèmes algébriques que l'on met de nombreuses années à résoudre, car les conjectures résistent avec une énergie farouche.
Le problème des quatre couleurs, décrit pour la première fois par le mathématicien anglais A. Cayley en 1879 dans le volume I des comptes rendus de la Société royale de géographie, est de ceux que Franck Harary appelle graphical disease.
Il s'agit de démontrer une propriété conjecturée, semble-t-il pour la première fois par Francis Guthrie, en 1852 : alors qu'il cherchait à colorier les « départements » d'une carte de l'Angleterre en utilisant le plus petit nombre de couleurs possibles, mais en évitant que deux départements ayant une frontière commune soient de la même couleur, F. Guthrie a été surpris de constater que quatre couleurs seulement lui étaient nécessaires. Serait-ce une propriété particulière des départements anglais, ou bien une propriété commune à toutes les cartes de géographie ?
Démontrer que l'on peut toujours le faire avec cinq couleurs s'est avéré très facile. Mais avec quatre couleurs, il s'agissait d'une tout autre histoire... et qui a suscité des flots considérables d'argumentation – et de preuves fausses ! Plusieurs ouvrages sont cependant consacrés à l'ensemble des propriétés qui en découlent. Ce problème entre dans le cadre de la théorie des graphes au moyen de la transformation indiquée sur la figure. À chaque département on fait correspondre un sommet du graphe, et l'on trace une arête entre deux sommets toutes les fois que les départements ont une frontière commune non réduite à un point. Trouver un coloriage de la carte en quatre couleurs revient à trouver une application C de l'ensemble des sommets dans {1, 2, 3, 4}, […]
… pour nos abonnés, l'article se prolonge sur 5 pages…
