. . . . . . . "En th\u00E9orie des graphes, le th\u00E9or\u00E8me de Gallai-Hasse-Roy-Vitaver \u00E9nonce une dualit\u00E9 entre les colorations des sommets d'un graphe non orient\u00E9 donn\u00E9 et les orientations de ses ar\u00EAtes. Il dit que le nombre minimum de couleurs n\u00E9cessaires pour colorer un graphe G (son nombre chromatique) est \u00E9gal \u00E0 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."@fr . . "12000"^^ . . . . . "En th\u00E9orie des graphes, le th\u00E9or\u00E8me de Gallai-Hasse-Roy-Vitaver \u00E9nonce une dualit\u00E9 entre les colorations des sommets d'un graphe non orient\u00E9 donn\u00E9 et les orientations de ses ar\u00EAtes. Il dit que le nombre minimum de couleurs n\u00E9cessaires pour colorer un graphe G (son nombre chromatique) est \u00E9gal \u00E0 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\u00E9quences du th\u00E9or\u00E8me est que toute orientation d'un graphe de nombre chromatique k contient un chemin orient\u00E9 simple avec k sommets ; ce chemin peut \u00EAtre forc\u00E9 \u00E0 commencer en n'importe quel sommet \u00E0 partir duquel on peut atteindre tous les autres sommets du graphe orient\u00E9."@fr . . . . "189767990"^^ . . . . . . . . . . . . . . . . . "Th\u00E9or\u00E8me de Gallai-Hasse-Roy-Vitaver"@fr . . "13785591"^^ . . . . .