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.