Séminaire du LIF
Jeudi 24 février à 14h - Luminy, Amphi 12
Frédéric Mazoit
EP, Université de Nantes
Décompositions en branches et graphes planaires
Dans leur longue série d'articles sur les mineurs de graphes, Robertson et Seymour on 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.
Frédéric Mazoit. Décompositions algorithmiques des graphes. Thèse de Doctorat, LIP, ENS Lyon, 16 déc 2004. www.ens-lyon.fr/LIP/Pub/Rapports/PhD/PhD2004/PhD2004-08.pdf
Email : Frederic.Mazoit@univ-nantes.fr