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 (graphcoloringoriented coloringacyclic coloringimproper coloringcoloring gamegraph product)