Evènement pour le groupe GT Graphes et Applications


Date 2016-01-15  14:00-15:00
TitreColoration aléatoire de graphes peu denses 
RésuméD'après le théorème de Brooks, le nombre chromatique d'un graphe est presque toujours inférieur à son degré maximum. En 1998, Reed a montré que cette borne pouvait être affinée de façon à remplacer le degré maximum par la taille d'une clique maximum dans une fraction de la borne. En d'autres termes, on peut toujours économiser un nombre de couleurs proportionnel à l'écart entre le degré maximum et la taille d'une clique maximum. Ici, on s'intéresse à une étape clé de la preuve correspondante ; comment colorer économiquement un graphe dans lequel aucun sommet ne "voit beaucoup d'arêtes" dans son voisinage ? Nous améliorons la méthode probabiliste utilisée dans ce cas, et appliquons notamment le résultat à la coloration forte d'arêtes (coloration d'arêtes telle qu'aucune arête n'est incidente à deux arêtes de même couleur). Erdos et Nesetril ont conjecturé en 1989 que tout graphe de degré maximum D admet une coloration forte d'arêtes avec 1.25 D^2 couleurs, quand la borne supérieure triviale est de 2 D^2. Notre méthode permet d'améliorer significativement la borne existante (Bruhn et Joos, 2015), ainsi que le théorème de Reed. Ces travaux sont le fruit d'une collaboration avec Thomas Perrett (Technical University of Denmark) et Luke Postle (University of Waterloo).  
LieuSalle 178 
OrateurMarthe Bonamy 



Aucun document lié à cet événement.

Retour
Retour à l'index