Book contents
- Frontmatter
- Contents
- Preface
- 1 Hereditary and monotone properties of combinatorial structures
- 2 Ordering classes of matrices of 0's and 1's
- 3 Cycle decompositions of complete graphs
- 4 Excluding induced subgraphs
- 5 Designs and topology
- 6 The number of points on an algebraic curve over a finite field
- 7 On the efficient approximability of constraint satisfaction problems
- 8 The combinatorics of cryptographic key establishment
- 9 Bandwidth of graphic matroids
9 - Bandwidth of graphic matroids
Published online by Cambridge University Press: 16 March 2010
- Frontmatter
- Contents
- Preface
- 1 Hereditary and monotone properties of combinatorial structures
- 2 Ordering classes of matrices of 0's and 1's
- 3 Cycle decompositions of complete graphs
- 4 Excluding induced subgraphs
- 5 Designs and topology
- 6 The number of points on an algebraic curve over a finite field
- 7 On the efficient approximability of constraint satisfaction problems
- 8 The combinatorics of cryptographic key establishment
- 9 Bandwidth of graphic matroids
Summary
Abstract
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 (E1, E2) be a partition of E. The border of (E1, E2) is the set of vertices which belong to both an edge of E1 and an edge of E2. We denote this by δ(E1, E2), or simply by δ(E1).
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.
- Type
- Chapter
- Information
- Surveys in Combinatorics 2007 , pp. 275 - 286Publisher: Cambridge University PressPrint publication year: 2007
- 2
- Cited by