Branchwidth of graphic matroids - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Book Sections Year : 2007

Branchwidth of graphic matroids

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.
Fichier principal
Vignette du fichier
Branchwidth.pdf (149.11 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

lirmm-00325145 , version 1 (31-08-2010)

Identifiers

Cite

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⟩
160 View
329 Download

Altmetric

Share

Gmail Facebook X LinkedIn More