Evènement pour le groupe GT Graphes et Applications


Date 2007-12-14  14:00-15:00
TitreUne relaxation du problème de Havel 
RésuméEn 1976, Appel et Haken ont prouvé que tout graphe planaire est 4-coloriable. Grötzsch quant à lui a montré que tout graphe planaire sans triangle est 3-coloriable en 1963. En 1970, Havel s'interroge sur le problème suivant : si on prend un graphe planaire G contenant des triangles, mais ceux-ci étant suffisamment éloignés les uns des autres ; est-ce que G est 3-coloriable ? Existe t-il une constante d telle que tout graphe planaire ayant leurs triangles à distance au moins d est 3-coloriable ? À ce jour, personne n'a démontré l'existence de d, ni n'a proposé de contre-exemples pour d quelconque. Dans cet exposé, nous proposerons une relaxation du problème de Havel et tenterons d'apporter quelques réponses à cette relaxation.  
LieuSalle 75 
OrateurMickaël Montassier 
UrlLaBRI 



Aucun document lié à cet événement.

Retour
Retour à l'index