vignette|upright=1.3| Quatre orientations différentes d'un 5-cycle, montrant un sous-graphe acyclique maximal pour chaque orientation (arêtes pleines) et une coloration des sommets par la longueur du plus long chemin entrant dans ce sous-graphe. L'orientation avec les chemins les plus courts, à gauche, permet également une coloration optimale du graphe. En théorie des graphes, le théorème de Gallai-Hasse-Roy-Vitaver énonce une dualité entre les colorations des sommets d'un graphe non orienté donné et les orientations de ses arêtes. Il dit que le nombre minimum de couleurs nécessaires pour colorer un graphe G (son nombre chromatique) est égal à 1 plus la longueur du plus long chemin dans une orientation de G choisie pour minimiser la longueur de ce chemin.. Les orientations pour lesquelles le chemin le plus long a une longueur minimale comprennent toujours au moins une orientation acyclique..

Une des conséquences du théorème est que toute orientation d'un graphe de nombre chromatique k contient un chemin orienté simple avec k sommets. ; ce chemin peut être forcé à commencer en n'importe quel sommet à partir duquel on peut atteindre tous les autres sommets du graphe orienté...

Exemples

Un graphe biparti peut être orienté d'un côté de la bipartition vers l'autre; le plus long chemin dans cette orientation n'a que deux sommets. Réciproquement, si un graphe est orienté sans avoir de chemin à trois sommets, alors chaque sommet doit être soit une source (sans arêtes entrantes) soit un puits (sans arêtes sortantes) et la partition des sommets en sources et puits montre qu'il est biparti. Dans toute orientation d'un graphe cycle de longueur impaire, l'orientation des arêtes ne peut pas alterner le long du cycle, donc il y a deux arêtes consécutives qui forment un chemin à trois sommets. Ceci correspond au fait que le nombre chromatique d'un cycle impair est trois.

Démonstration On prouve d'abord que le nombre chromatique est supérieur ou égal au nombre minimum de sommets dans un chemin de longueur maximale. Supposons qu'un graphe donné ait une coloration avec k couleurs, pour un certain nombre k . Il peut alors être orienté de manière acyclique en numérotant les couleurs et en dirigeant chaque arête de son extrémité de numéro inférieur vers l'extrémité de numéro supérieur. Avec cette orientation, les nombres augmentent strictement le long de chaque chemin orienté, et donc il contient au plus k sommets.

On prouve réciproquement que le nombre chromatique est inférieur ou égal au nombre minimum de sommets dans un chemin le plus long. Supposons qu'un graphe donné ait une orientation avec au plus k sommets par chemin orienté simple, pour un entier k . Les sommets du graphe peuvent alors être colorés avec k couleurs en choisissant un sous- graphe acyclique maximal pour l'orientation, puis en colorant chaque sommet par la longueur du chemin le plus long dans le sous-graphe choisi qui se termine en ce sommet. Chaque arête du sous-graphe est orientée d'un sommet avec un nombre inférieur à un sommet avec un nombre plus élevé, et est donc correctement colorée. Pour chaque arête qui n'est pas dans le sous-graphe, il existe un chemin du sous-graphe reliant les deux mêmes sommets dans la direction opposée, sinon l'arête aurait pu être incluse dans le sous-graphe choisi; par conséquent, l'arête est orientée d'un entier plus grand vers un entier plus petit et est à nouveau correctement colorée.

La preuve de ce théorème a été utilisée comme test dans le cadre d'une formalisation du l'induction mathématique par Youri Matiiassevitch..

Interprétation dans la théorie des catégories Le théorème a également une interprétation naturelle dans la catégorie des graphes orientés et des homomorphismes de graphes (un homomorphisme est une application des sommets d'un graphe dans les sommets d'un autre qui envoie toujours une arête sur une arête). Ainsi, une k- coloration d'un graphe non orienté G peut être décrite par un homomorphisme de G dans le graphe complet K k . Si le graphe complet est orienté, il est un tournoi, et l'orientation peut être remontée à travers l'homomorphisme pour donner une orientation dans G. En particulier, la coloration donnée par la longueur du plus long chemin entrant correspond ainsi à un homomorphisme dans un tournoi transitif (un graphe complet orienté acyclique), et chaque coloration peut être décrite par un homomorphisme sur un tournoi transitif de cette manière.

En considérant les homomorphismes dans l'autre sens, c'est-à-dire vers G au lieu de depuis G, un graphe orienté G est acyclique et a au plus k sommets dans son chemin le plus long si et seulement s'il n'y a pas d'homomorphisme à partir du graphe chemin P k + 1 dans G.

Ainsi, le théorème de Gallai-Hasse-Roy-Vitaver peut être formulé de manière équivalente comme suit: Pour tout graphe orienté G, il existe un homomorphisme de G vers le tournoi transitif à k sommets si et seulement s'il n'existe pas d'homomorphisme du graphe chemin à k + 1 sommets vers G. Dans le cas où G est acyclique, cela peut également être vu comme une façon d'énoncer le théorème de Mirsky-Newman selon lequel la longueur de la plus longue chaîne dans un ensemble partiellement ordonné est égale au nombre minimum d'antichaînes dans lesquelles l'ensemble peut être partitionné.. Cet énoncé peut être généralisé des chemins aux graphes orientés : pour chaque polyarbre P il existe un graphe orienté dual D tel que, pour tout graphe orienté G, il y a un homomorphisme de G dans D si et seulement s'il n'y a pas d'homomorphisme de P dans G.. Note historique Le théorème de Gallai-Hasse-Roy-Vitaver a été redécouvert à plusieurs reprises. Il est nommé d'après des publications séparées de Tibor Gallai., Maria Hasse., Bernard Roy., et L. M. Vitaver.. Roy attribue l'énoncé du théorème à une conjecture dans l'ouvrage de théorie des graphes. de Claude Berge.

Références

Gallai-Hasse-Roy-Vitaver Catégorie:Coloration d'un graphe