Branchwidth of graphic matroids.

Frédéric Mazoit (1) , Stéphan Thomassé (2)

1 LIF - Laboratoire d'informatique Fondamentale de Marseille - UMR 6166
2 MASCOTTE - Algorithms, simulation, combinatorics and optimization for telecommunications

Answering a question of Geelen, Gerards, Robertson and Whittle, we prove that the branchwidth of a bridgeless graph is equal to the branch- width of its cycle matroid. Our proof is based on branch-decompositions of hypergraph.

Mots clés: branchwidth; graphic matroid

Domaines: Mathématique discrète [cs.DM]

Frédéric Mazoit, Stéphan Thomassé. Branchwidth of graphic matroids.. 2005. ⟨hal-00012312⟩