Retour à l'index du GREYC

Séminaire Algorithmique

Site du CNRS

Séminaire Algorithmique

Le séminaire a lieu le mardi à 11 h 45 (sauf modification exceptionnelle), au campus Côte de Nacre, bâtiment Sciences 3, salle S3 351, 3ème étage.

Résumé du séminaire du Mardi 1 Mars 2005

Décompositions en branches et graphes planaires

par Frédéric Mazoit (LIP, ENS Lyon)

Dans leur longue série d'articles sur les mineurs de graphes, Robertson et Seymour ont défini une nouvelle classe de décompositions des graphes -- les décompositions en branches -- pour obtenir une obstruction aux décompositions arborescente. Cette obstruction a permis à Seymour et Thomas, en calculant exactement la largeur de branches des graphes planaires, de donner la meilleure approximation de la largeur arborescente des graphes planaires.

Je montrerai comment unifier ces deux types de décompositions à l'aide d'un nouvel objet combinatoire : les matriochkas. Ces matriochkas permettent de mieux comprendre les liens mais aussi les différences entre les décompositions arborescentes et les décompositions en branches. En les utilisant, il est aussi possible de transférer des résultats d'une des décompositions à l'autre. Je présenterai une nouvelle démonstration du fait que la largeur arborescente d'un graphe planaire et celle de son dual diffèrent au plus d'un, démonstration que j'ai obtenue de cette façon.

GREYC
Campus Côte de Nacre, boulevard du Maréchal Juin
BP 5186
14032 Caen Cedex
FAX : +33 (0)2 31 56 73 30
http://www.greyc.fr