Le Théorème de Gallai-Roy affirme que tout graphe oriente
de nombre
chromatique n (i.e. n-colorable mais non (n-1)-colorable) contient un chemin
oriente direct de longueur n-1.
Dans une premiere partie, nous examinerons une conjecture plus forte
de Laborde, Payan et Xuong qui affirme que tout graphe oriente a un stable
intersectant tous les plus longs chemins directs.
Dans une seconde partie, nous etudierons les graphes orientes
n-universels, c'est a dire contenu dans tous les graphes orientes
de nombre
chromatique n.
Nous montrerons en particulier que les chemins a deux blocs de longueur n-1 sont n-universels. Ce dernier resultat a ete obtenu avec L. Addario-Berry et
S. Thomasse.