Evènement pour le groupe GT Graphes et Applications


Date 2015-06-19  14:00-15:00
Titre Immersions de digraphes 2-réguliers vs. mineurs de graphes (d'après Matt DeVos) 
RésuméUn digraphe est 2-régulier si tous ses sommets sont de degré entrant 2 et de degré sortant 2. Il est possible d'associer un tel digraphe D(G) à tout graphe non orienté G plongé dans une surface orientable (nous verrons comment). Les opérations de suppression et contraction d'arête dans G ont alors un équivalent simple dans D(G) en termes de "séparation de sommet" (splitting). Le théorème de Robertson et Seymour -- qui établit que toute famille de graphes close par mineurs est caractérisée par un ensemble fini de mineurs exclus -- trouve une expression similaire dans le cas des digraphes 2-reguliers mais avec un ensemble de configurations exclues de taille bien moindre : une seule dans le cas du plan (contre deux pour les mineurs de graphes, les fameux K_5 et K_{3,3}), 4 pour le plan projectif (contre 35) et peut-être une dizaine (contre plus de 10000, non résolu à ce jour) pour le tore.  
LieuSalle 76 
OrateurEric Sopena 



Aucun document lié à cet événement.

Retour
Retour à l'index