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é:   
Large rank-width and circle graphs as vertex-minors
du groupe Séminaire-Ecole sur les décompositions des graphes

Date 2008-04-03  14:00-15:30
TitreLarge rank-width and circle graphs as vertex-minors 
RésuméRésumé plus précis et RAPPEL L'inclusion des graphes au sens des "vertex-minors" est une notion analogue à l'inclusion au sens des mineurs, tout comme la largeur de rang ("rank-width") est analogue à la largeur arborescente. On conjecture que les graphes d'intersection des cordes d'un cercle ("circle graph") jouent , par rapport à la largeur de rang, un rôle semblable à celui des graphes planaires par rapport à la largeur arborescente, et que les graphes qui ne contiennent pas comme "vertex minor " un graphe d'intersection de cordes donné sont de largeur de rang bornée. Ce résultat généraliserait "Graph Minors V". Il est montré dans l'exposé pour les "line graphs" (graphes d'incidences) et les graphes d'intersection de cordes bipartis. La conjecture reste ouverte. Résumé fait par B. Courcelle  
LieuAmphi LaBRI 
OrateurSang-Il OUM 
UrlKAIST, Corée 



Aucun document lié à cet événement.

Retour
Retour à l'index