 |
 |
|
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 |
Titre | Large 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
|
Lieu | Amphi LaBRI |
Orateur | Sang-Il OUM |
Url | KAIST, Corée |
Aucun document lié à cet événement. RetourRetour à l'index
| |