Evènement pour le groupe Séminaire du LaBRI


Date 2008-04-03  14:00-15:00
TitreSéminaire LaBRI, Sang-il Oum, Line graphs of large rank-width 
Résumé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 



Aucun document lié à cet événement.

Retour
Retour à l'index