Skip to Main content Skip to Navigation
Book sections

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.
Document type :
Book sections
Complete list of metadata

Cited literature [6 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00325145
Contributor : Stephan Thomasse <>
Submitted on : Tuesday, August 31, 2010 - 3:19:28 PM
Last modification on : Thursday, February 7, 2019 - 2:20:28 PM
Long-term archiving on: : Wednesday, December 1, 2010 - 2:16:11 AM

File

Branchwidth.pdf
Files produced by the author(s)

Identifiers

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⟩

Share

Metrics

Record views

294

Files downloads

385