Evènement pour le groupe GT Graphes et Applications


Date 2012-02-24  14:00-15:00
TitreDes limites de la coloration quasi propre 
RésuméUne coloration quasi propre est une coloration des sommets où chaque classe de couleurs induit un sous graphe de degré maximum fixé. Dans cet exposé, nous nous intéresserons au cas où les couleurs sont de deux types: a couleurs induisant un sous graphe de degré maximum d, et b couleurs induisant un stable (coloration propre): on parle de (d,a,b)*-coloration. Nous montrons que tout graphe dont le mad (degré moyen maximum) est inférieur à une certaine fonction f est (d,a,b)*-coloriable. Cette fonction f tend (par valeurs inférieures) vers 2a+b quand d tend vers l'infini. Ce résultat est asymptotiquement optimal : il existe des graphes non (d,a,b)*-coloriables dont le mad tend (par valeurs inférieures également) vers 2a+b. Ceci montre en quelque sorte qu'en terme de degré moyen, une couleur d-impropre n'est pas plus efficace que deux couleurs propres.  
LieuSalle 178 
OrateurDorbec et/ou Montassier (voire Raspaud) 
UrlLaBRI 



Aucun document lié à cet événement.

Retour
Retour à l'index