Titre : Colorations d'incidences par listes
Encadrant : Éric Sopena
Laboratoire : LaBRI
Équipe de recherche : Combinatoire et Algorithmique (thème
Graphes et Applications)
Description détaillée :
Soit G un graphe ayant pour ensemble de sommets V(G) et pour ensemble d'arêtes E(G).
Une incidence de G est un couple (v, e) ou v est un sommet
et e une arête incidente
à v (si G a m arêtes, il a ainsi 2m
incidences). Deux incidences (v, e) et (w, f)
sont considérées comme adjacentes
si l'une des conditions suivantes est vérifiée :
(1) e = f (i.e. v et w sont les extrémités d'une même arête),
(2) v = w (i.e. e et f
sont incidentes à un même sommet) ou
(3) e = (v, w) (i.e. les 2 incidences sont les
deux premières moitiés de deux arêtes
consécutives). Une coloration des incidences
de G est alors une fonction qui
associe à chaque incidence de G une couleur de façon
telle que deux incidences
adjacentes ont des couleurs distinctes.
Les colorations d'incidences ont été introduites par Brualdi
et Massey en 1993 et
étudiées par la suite par plusieurs
auteurs qui ont notamment considéré le nombre
chromatique d'incidence de différentes
classes de graphes.
Le but de cette thèse est de considérer l'extension de ces
colorations au cas des
colorations par listes. La notion
de coloration par listes est une généralisation
classique des problèmes de
coloration : on associe à chaque élément à colorier
(ici à chaque incidence) une liste
de couleurs et on cherche à colorier le graphe
de façon à utiliser pour chaque élément
une couleur prise dans la liste qui lui
est associée.
Un graphe sera ainsi dit « k-liste-coloriable » si, pour
toute affectation de listes
de taille k, il existe une
coloration du graphe compatible avec cette affectation.
Le nombre chromatique par liste d'un graphe est alors le
plus petit entier k pour
lequel le graphe est k-liste-coloriable.
Cette notion de coloration par liste, classique dans
d'autres contextes, na à ce
jour pas été étudiée dans le cadre des colorations d'incidence.