Evènement pour le groupe GT Graphes et Applications


Date 2013-03-22  14:00-15:00
TitreColoration localement irrégulière des arêtes d’un graphe 
RésuméUne problématique récurrente de la théorie des graphes est celle de la distinction des sommets voisins au sein d’un graphe. Le principe consiste à colorer les éléments du graphe en respectant un ensemble de contraintes, et ce de sorte que deux de ses sommets voisins soient distinguables grâce à la coloration obtenue. Deux paramètres entrent donc en jeu, à savoir le type de coloration ainsi que les conditions faisant que l’on considère deux sommets comme distingués. Plusieurs variantes du problème ont été étudiées pour des définitions précises de ces deux paramètres. Dans notre version du problème, nous ne colorons que les arêtes du graphe et nous considérons que deux de ses sommets sont distingués s’ils sont de degrés différents dans le sous-graphe induit par la couleur de l’arête les joignant. Une coloration des arêtes permettant de distinguer deux sommets voisins de cette manière est dite localement irrégulière. Tout graphe n’admet pas de coloration localement irrégulière de ses arêtes. En revanche, nous conjecturons que tout graphe colorable (au sens de la coloration d’arêtes localement irrégulière) admet une telle coloration utilisant au plus 3 couleurs. Dans cet exposé, nous montrerons tout d’abord que cette conjecture est vraie pour diverses familles de graphes. Puis, nous prouverons que même si cette conjecture était vraie, le problème de déterminer s’il existe une coloration localement irrégulière des arêtes d’un graphe utilisant au plus 2 couleurs resterait NP-complet en général. Travail réalisé en collaboration avec O. Baudon, J. Przybylo, E. Sopena et M. Wozniak.  
LieuSalle 178 
OrateurJulien Bensmail 
UrlLaBRI 



Aucun document lié à cet événement.

Retour
Retour à l'index