Abstract FR:

Une coloration oriente d'un graphe oriente g est une application de l'ensemble des sommets de g vers un ensemble de couleurs c telle que : i) si (x,y) est un arc dans g alors la couleur de x est differente de la couleur de y ii) si (x,y) et (u,v) sont des arcs dans g et que la couleur de x est identique a la couleur de v alors la couleur de y est differente de la couleur de u. On definit le nombre chromatique oriente d'un graphe g comme le nombre minimum de couleurs necessaires pour colorier g. Une coloration peut etre vue comme un homomorphisme d'un graphe oriente g vers un graphe oriente h, appele graphe des couleurs. Nous nous sommes interessee a plusieurs types de colorations orientees et non orientees. Nous avons tout d'abord etudie les colorations orientees de certaines familles de graphes comme les graphes de degre au plus trois et les graphes de halin. Nous avons generalise la notion de coloration orientee (ou coloration p#2-preservante) aux colorations t-preservantes. Il s'agit de colorier de couleurs distinctes tous les sommets qui appartiennent a un sous-graphe isomorphe au graphe t. Nous avons egalement etudie les colorations impropres acycliques de graphes non orientes pour de nombreuses familles de graphes. Ces colorations generalisent la notion de coloration acyclique. Enfin, nous avons regarde l'aspect algorithmique de la coloration orientee en considerant les colorations orientees incrementales. Dans tous les cas, nous cherchons principalement a borner le nombre minimum de couleurs necessaires pour colorier un graphe.