Bandwidth of graphic matroids
Frédéric Mazoit, Stéphan Thomassé · Cambridge University Press eBooks · 2007
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. Introduction . The notion of branchwidth was introduced by Robertson and Seymour in their seminal paper Graph Minors X [3]. Very roughly speaking, the goal is to decompose a structure S along a tree T in such a way that subsets of S corresponding to disjoint branches of T are pairwise as disjoint as possible. One can define the branchwidth of various structures such as graphs, hypergraphs, matroids, submodular functions … Our goal in this paper is to prove that the definitions of branchwidth for graphs and matroids coincide in the sense that the branchwidth of a bridgeless graph is equal to the branchwidth of its cycle matroid. This answers a question of Thomas [5], also cited in Geelen, Gerards, Robertson and Whittle [1]. Let us now define properly these notions. Let H = ( V, E ) be a graph, or a hypergraph, and ( E 1 , E 2 ) be a partition of E . The border of ( E 1 , E 2 ) is the set of vertices which belong to both an edge of E 1 and an edge of E 2 . We denote this by δ( E 1 , E 2 ), or simply by δ( E 1 ). A branch-decomposition T of H is a ternary tree T and a bijection from the set of leaves of T into the set of edges of H .