Branchwidth of graphic matroids

Frédéric Mazoit 1 Stéphan Thomassé 2
2 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : Answering a question of Geelen, Gerards, Robertson and Whittle, we prove that the branchwidth of a bridgeless graph is equal to the branchwidth of its cycle matroid. Our proof is based on branch-decompositions of hypergraphs. By matroid duality, a direct corollary of this result is that the branchwidth of a bridgeless planar graph is equal to the branchwidth of its planar dual. This consequence was a direct corollary of a result by Seymour and Thomas.
Type de document :
Chapitre d'ouvrage
Surveys in Combinatorics 2007, 346, pp.275-286, 2007, 9780511666209. 〈10.1017/CBO9780511666209.010〉
Liste complète des métadonnées

Littérature citée [6 références]  Voir  Masquer  Télécharger

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00325145
Contributeur : Stephan Thomasse <>
Soumis le : mardi 31 août 2010 - 15:19:28
Dernière modification le : jeudi 11 janvier 2018 - 06:26:13
Document(s) archivé(s) le : mercredi 1 décembre 2010 - 02:16:11

Fichier

Branchwidth.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Citation

Frédéric Mazoit, Stéphan Thomassé. Branchwidth of graphic matroids. Surveys in Combinatorics 2007, 346, pp.275-286, 2007, 9780511666209. 〈10.1017/CBO9780511666209.010〉. 〈lirmm-00325145〉

Partager

Métriques

Consultations de la notice

196

Téléchargements de fichiers

294