|
Evènement pour le groupe Séminaire du LaBRI
Date | 2008-04-03 14:00-15:00 |
Titre | Sé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 |
Lieu | Amphi LaBRI |
Orateur | Sang-il Oum |
Aucun document lié à cet événement. RetourRetour à l'index
| |