Cette thèse propose un modèle général de parcours de graphe à base de tie-break sur des ensembles d'étiquettes. Par ailleurs nous étudions la structure des graphes de cocomparabilité (graphes dont les complémentaires sont ordonnables transitivement). En particulier nous les caractérisons à l'aide de la théorie des treillis des antichaînes maximales. Nous montrons commnt calculer simplement à l'iade de parcours de graphes certaines propriétés des graphes de cocomparabilité. Enfin nous proposons deux nouveaux parcours lexicographiques de graphes LEXUP, LEXDOWN dont nous établissons les premières propriétés.