Actualités
  Période
semaine
ou mois
aucune période


  Thèmes:
Thèses
Colloques
Autres
Groupes
Tous les thèmes

   
  Liens:
Voir les thèses

Voir les colloques

Voir les autres événements

Voir la page des groupes

Accéder à l'intranet

Intitulé:   
Immersions de digraphes 2-réguliers vs. mineurs de graphes (d'après Matt DeVos)
du 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