Homomorphismes et colorations de graphes orientés
Arc-colorations de graphes orientés
Colorations impropres acycliques
Dernière mise à jour le 26 décembre 2008
Mes activités de recherche se déroulent au sein de l’équipe Combinatoire et Algorithmique du LaBRI, et plus précisément
au sein du thème Graphes &
Applications. Mes principaux centres d’intérêt actuels concernent
les colorations de graphes et sont décrits ci-dessous.
De façon classique, une k-coloration propre d’un graphe non orienté G peut être vue comme un homomorphisme de G vers le graphe complet à k sommets. En considérant les homomorphismes de graphes orientés (antisymétriques), nous obtenons une nouvelle notion de coloration des graphes orientés : une k-coloration c d’un graphe orienté antisymétrique G associe à chaque sommet de G une couleur prise dans l’ensemble {1,2,...,k} de façon telle que (i) les sommets adjacents ont des couleurs distinctes et (ii) si xy et zt sont deux arcs de G tels que c(x) = c(t), alors c(y) <> c(z) (en d’autres termes, les couleurs des extrémités déterminent l’orientation d’un arc). Le nombre chromatique orienté d’un graphe G est alors défini comme le nombre minimum de couleurs nécessaires pour colorier G. Le nombre chromatique orienté d’un graphe non orienté est défini comme le nombre maximum des nombres chromatiques orientés de ses orientations.
L’un des principaux « challenges » dans ce domaine est la détermination du nombre chromatique orienté de la famille des graphes planaires, dont nous savons qu’il se situe entre 18 et 80…
Par analogie avec le cas non orienté, une arc-coloration d’un graphe orienté (antisymétrique) G est une (sommet-) coloration du graphe représentatif des arcs de G. Une telle coloration associe ainsi une couleur à chaque arc de G de façon telle que (i) deux arcs consécutifs xy et yz sont de couleurs distinctes et (ii) si xy et vw sont deux arcs de même couleur alors deux arcs de la forme yz et uv ne peuvent avoir la même couleur. Le nombre minimum de couleurs nécessaires à une telle coloration de G est l’index chromatique orienté de G.
Une coloration d’un graphe non orienté G est dite acyclique si tout cycle de G utilise au moins trois couleurs. En d’autres termes, pour toute paire de couleurs distinctes a et b, le sous-graphe de G induit par les éléments de couleur a ou b est une forêt. Cette propriété peut être étudiée dans le cas des colorations de sommets ou des colorations d’arêtes. On parle alors respectivement de nombre chromatique acyclique ou d’index chromatique acyclique.
Une (sommet-) coloration impropre d’un graphe non orienté G permet à des sommets voisins de se voir affecter la même couleur, selon certaines conditions imposées sur les sous-graphes induits par les sommets de même couleur. Une telle coloration est dite acyclique si pour tout couple de couleurs distinctes (a,b), le sous-graphe de G induit par les arêtes ayant une extrémité coloriée a et l’autre coloriée b est une forêt. En d’autres termes, aucun cycle pair de G n’est « bicolore alterné ».
Une incidence d’un graphe non orienté G est un couple de la forme (v,e) où v est un sommet de G et e une arête de G incidente à v. Deux incidences (v,e) et (w,f) sont adjacentes si (i) v = w, (ii) e = f ou (iii) vw = e ou f. Une coloration d’incidence de G associe à chaque incidence de G une couleur de façon telle que deux incidences adjacentes ont des couleurs distinctes. Le nombre chromatique d’incidence de G est défini comme le nombre minimum de couleurs nécessaires pour une telle coloration.
Soit G un graphe non orienté et G* le graphe orienté obtenu à partir de G remplaçant chaque arête de G par deux arcs opposés. Une incidence (v,e) de G, avec e = vw, peut alors être associée avec l’arc vw de G*. Ainsi, une coloration d’incidence de G peut être vue comme une coloration des arcs de G* de façon telle que (i) des arcs sortant d’un même sommet ont des couleurs distinctes et (ii) deux arcs consécutifs ont des couleurs distinctes. Ainsi, pour toute couleur c, le sous-graphe de G* induit par les arcs de couleur c est une forêt d’étoiles (dont tous les arcs sont dirigés vers le centre). Le nombre chromatique d’incidence de G correspond ainsi à l’étoile-arboricité du graphe G*.
Nombre chromatique orienté « ludique ». Soit G un graphe orienté et C un ensemble de k couleurs. Deux joueurs, Alice et Bob, choisissent à tour de rôle un sommet x de G et lui affectent une couleur de C de façon telle que (i) la coloration partielle induite respecte les règles de coloration orientée et (ii) si xy et yz (resp. zy et yx) sont deux arcs de G, alors la couleur affectée à x doit être différente de celle de z (dans le cas où le sommet z a déjà été colorié). Alice est déclarée gagnante si et seulement si le graphe G est colorié en totalité (l’objectif de Bob est donc de l’empêcher d’obtenir une telle coloration). Le nombre chromatique orienté ludique de G est alors défini comme le plus petit entier k pour lequel Alice a une stratégie gagnante.
Jeux de coloration combinatoires. Considérons le jeu combinatoire suivant. Soit G un graphe non orienté, C un ensemble de k couleurs et Alice et Bob nos deux joueurs. À tour de rôle, chaque joueur choisit un sommet de G non colorié et lui affecte une couleur de façon à ce que la coloration partielle obtenue soit propre. Le premier joueur ne pouvant plus jouer est déclarant perdant (version dite normale).
Lorsque k = 1, chaque coup revient à supprimer un sommet ainsi que l’ensemble de ses voisins, et le jeu se termine lorsque le graphe est devenu vide. Si, de plus, le graphe G de départ est une chaîne, nous retrouvons le jeu combinatoire classique Node-Kayles.