Titre du sujet : Sur
quelques problèmes de colorations orientées
Nom du responsable : Éric SOPENA, sopena@labri.fr, 05 40 00 38 71
Équipe du LaBRI : Combinatoire et Algorithmique, thème
« Graphes et Applications »
Financement : candidature sur allocations de recherche
ministérielles
Description détaillée du sujet
On s’intéresse ici aux colorations de
graphes orientés (antisymétriques), définies de la façon suivante :
une k-coloration d’un graphe orienté G
est une application qui associe à chaque sommet de G une couleur prise
dans l’ensemble {1,2,…,k} de façon telle que (1) si xy
est un arc de G, x et y ont des couleurs distinctes et (2)
si xy et zt
sont deux arcs de G tels que x et t sont de même couleur
alors y et z doivent avoir des couleurs distinctes. Le nombre
chromatique orienté de G est alors défini comme le plus petit nombre
de couleurs nécessaire pour obtenir une telle coloration.
Les colorations orientées ont été
introduites il y a une quinzaine d’années et, depuis, étudiées par de nombreux
auteurs. Il reste cependant de nombreuses questions non résolues — ou non
encore considérées à ce jour — dans ce domaine, pour la plupart inspirées de
questions classiques de coloration des graphes non orientés. On pourra par
exemple s’intéresser aux pistes de recherche suivantes.
Colorations orientées de certaines
familles de graphes. La question principale ici est la détermination du nombre
chromatique orienté de la famille des graphes planaires (nous savons que ce nombre
est compris entre 17 et 80). Cette question est également toujours ouverte pour
d’autres familles de graphes particulières.
Produits de graphes. L’étude du
nombre chromatique des graphes produits est une question classique de
coloration, largement étudiée dans le cas des graphes non orientés mais non
encore considérée dans le cas des graphes orientés.
Colorations orientées impropres. Une coloration
est impropre lorsqu’on autorise les sommets voisins à recevoir des
couleurs identiques. On impose alors certaines contraintes sur les sous-graphes induits par les sommets de même couleur (on
peut par exemple demander que ces sous-graphes soient
des chemins, ou soient acycliques). Là encore, il s’agit d’un domaine largement
étudié dans le cas des graphes non orientés mais non encore considéré dans le
cas des graphes orientés.
Jeu de coloration. On considère le
jeu à deux joueurs suivant : Alice et Bob jouent à tour de rôle ;
chaque joueur doit choisir un sommet non colorié et lui associer une couleur
prise dans un ensemble de k couleurs fixé au départ ; Alice cherche
à produire une k-coloration du graphe alors
que Bob cherche à l’en empêcher. On cherche alors à déterminer, pour un graphe G
donné, le plus petit k pour lequel Alice a une stratégie gagnante, lui
permettant de produire une k-coloration de G
quelle que soit la stratégie de Bob. Dans le cas des graphes non orientés, ce
sujet a fait l’objet de nombreuses études, alors que quelques articles
seulement ont étudié ce jeu dans le cadre des colorations orientées. Plusieurs
techniques introduites dans le cas non orienté devraient pouvoir être adaptées
au cas orienté.
Arc-colorations orientées. Comme dans le
cas non orienté, une arc-coloration orientée peut
être définie comme une (sommet-) coloration du graphe représentatif des arcs.
Ce thème de recherche a été introduit dans la thèse d’Alexandre Pinlou (2006), mais de nombreuses questions restent encore
à explorer.
Sources bibliographiques
Nombreuses références sur les colorations
orientées, travaux de thèse de M. Hosseini Dolama, P. Ochem et A. Pinlou (voir www.labri.fr/perso/sopena/).
Mots-clés : graphe –
coloration – coloration orientée – coloration acyclique – coloration impropre –
jeu de coloration – produit de graphes (graph
– coloring – oriented coloring – acyclic coloring – improper coloring – coloring game – graph product)