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

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[1]. Les orientations pour lesquelles le chemin le plus long a une longueur minimale comprennent toujours au moins une orientation acyclique[2].

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.

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[3] ; ce chemin peut être forcé à commencer en n'importe quel sommet à partir duquel on peut atteindre tous les autres sommets du graphe orienté[4],[5].

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

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

Note historique

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.

Références
  1. Lih-Hsing Hsu et Cheng-Kuan Lin, Graph Theory and Interconnection Networks, Boca Raton, Florida, CRC Press, (ISBN 978-1-4200-4481-2, Math Reviews 2454502, lire en ligne), Theorem 8.5, P.129–130.
  2. Jaroslav Nešetřil et Patrice Ossona de Mendez, Sparsity: Graphs, Structures, and Algorithms, Heidelberg, Springer, coll. « Algorithms and Combinatorics » (no 28), (ISBN 978-3-642-27874-7, DOI 10.1007/978-3-642-27875-4, Math Reviews 2920058), page 42 Theorem 3.13.
  3. Gary Chartrand et Ping Zhang, Chromatic Graph Theory, Boca Raton, Florida, CRC Press, coll. « Discrete Mathematics and its Applications », (ISBN 978-1-58488-800-0, Math Reviews 2450569, lire en ligne), Theorem 7.17 (The Gallai–Roy–Vitaver Theorem).
  4. Hao Li, « A generalization of the Gallai–Roy theorem », Graphs and Combinatorics, vol. 17, no 4,‎ , p. 681–685 (DOI 10.1007/PL00007256, Math Reviews 1876576).
  5. Gerard J. Chang, Li-Da Tong, Jing-Ho Yan et Hong-Gwa Yeh, « A note on the Gallai–Roy–Vitaver theorem », Discrete Mathematics, vol. 256, nos 1–2,‎ , p. 441–444 (DOI 10.1016/S0012-365X(02)00386-2, Math Reviews 1927565).
  6. (ru) Ю. В. Матиясевич, Исследования по конструктивной математике и математической логике [« Studies in constructive mathematics and mathematical logic. Part VI. Dedicated to A. A. Markov on the occasion of his 70th birthday »], vol. 40, coll. « Zapiski Naučnyh Seminarov Leningradskogo Otdelenija Matematičeskogo Instituta im. V. A. Steklova Akademii Nauk SSSR (LOMI) »,‎ (Math Reviews 0363823), « Одна схема доказательств в дискретной математике », p. 94–100.
  7. Leon Mirsky, « A dual of Dilworth's decomposition theorem », American Mathematical Monthly, vol. 78, no 8,‎ , p. 876–877 (DOI 10.2307/2316481, JSTOR 2316481).
  8. Jaroslav Nešetřil et Claude Tardif, « A dualistic approach to bounding the chromatic number of a graph », European Journal of Combinatorics, vol. 29, no 1,‎ , p. 254–260 (DOI 10.1016/j.ejc.2003.09.024, Math Reviews 2368632).
  9. Tibor Gallai, « On directed graphs and circuits », dans Theory of Graphs (Proceedings of the Colloquium held at Tihany 1966), Budapest, Akadémiai Kiadó, , p. 115–118.
  10. (de) Maria Hasse, « Zur algebraischen Begründung der Graphentheorie. I », Mathematische Nachrichten, vol. 28, nos 5–6,‎ , p. 275–290 (DOI 10.1002/mana.19650280503, Math Reviews 0179105).
  11. Bernard Roy, « Nombre chromatique et plus longs chemins d'un graphe », ESAIM: Mathematical Modelling and Numerical Analysis - Modélisation Mathématique et Analyse Numérique, vol. 1, no 5,‎ , p. 129–132 (DOI 10.1051/m2an/1967010501291, Math Reviews 0225683, lire en ligne).
  12. (ru) Л. М. Витавер, « Нахождение минимальных раскрасок вершин графа с помощью булевых степеней матрицы смежностей [Determination of minimal coloring of vertices of a graph by means of Boolean powers of the incidence matrix] », Doklady Akademii Nauk SSSR, vol. 147,‎ , p. 758–759 (Math Reviews 0145509).
  13. Claude Berge, Théorie des graphes et ses applications, Paris, Dunod, (Math Reviews 102822, zbMATH 0088.15404).
    • Portail des mathématiques
    Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.