Théorème de Gallai-Hasse-Roy-Vitaver

• 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.

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[1].

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[6].

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[2]:

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é[7]. 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[8].

Le théorème de Gallai-Hasse-Roy-Vitaver a été redécouvert à plusieurs reprises[2]. Il est nommé d'après des publications séparées de Tibor Gallai[9], Maria Hasse[10], Bernard Roy[11], et L. M. Vitaver[12]. Roy attribue l'énoncé du théorème à une conjecture dans l'ouvrage de théorie des graphes[13] de Claude Berge.

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Gallai–Hasse–Roy–Vitaver theorem » (voir la liste des auteurs).