GRAPHES THÉORIE DES

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}, telle que deux sommets liés par une arête n'aient jamais la même image par C.

Quant à la propriété caractéristique des graphes associés aux cartes de géographie, nous la connaissons déjà : ils sont tous planaires.

Cette conjecture célèbre n'a été résolue par l'affirmative qu'en 1976, par Ken I. Appel et Wolfgang Haken. La démonstration, étant donné le nombre considérable des configurations réductibles à tester, a été en grande partie confiée à un ordinateur. C'est le premier exemple de théorème général obtenu par cette voie. Mais une telle démonstration posait un problème épistémologique : vu l'importance des moyens informatiques mis en œuvre, sa vérification était très difficilement reproductible. Cette difficulté a été levée par Neil Robertson, Daniel P. Sanders, Paul Seymour et Robin Thomas en 1996.

Les problèmes de coloration se sont enrichis récemment de la solution d'un problème qui, bien que n'ayant résisté que quarante-deux ans, a suscité les travaux d'une véritable armée de mathématiciens. La formulation de la conjecture est due à Claude Berge, à qui l'on doit certainement aussi l'introduction en France de la théorie des graphes, et la solution, toujours élégante, d'un grand nombre de problèmes.

Soit un graphe G non orienté fini. Une k-coloration de G est une coloration de ses sommets en k couleurs différentes, sous réserve que deux extrémités d'une même arête n'aient pas la même couleur. Par exemple, nous avons vu que les graphes planaires admettent tous au moins une 4-coloration. Une clique dans un graphe est un ensemble de sommets tels qu'il y ait toujours une arête entre deux quelconques d'entre eux (ex. K[...]