Unifying duality theorems for width parameters in graphs and matroids.
  I. Weak and strong duality

There is no author summary for this article yet. Authors can add summaries to their articles on ScienceOpen to make them more accessible to a non-specialist audience.

Abstract

We prove a general duality theorem for width parameters in combinatorial structures such as graphs and matroids. It implies the classical such theorems for path-width, tree-width, branch-width and rank-width, and gives rise to new width parameters with associated duality theorems. The highly connected substructures witnessing large width are presented in a unified way akin to tangles, as orientations of low-order separations satisfying certain consistency axioms.

Related collections

Most cited references 2

Record: found
Abstract: found
Article: found

Is Open Access

Connectivity and tree structure in finite graphs

Reinhard Diestel, Johannes Carmesin, Fabian Hundertmark … (2011)

Considering systems of separations in a graph that separate every pair of a given set of vertex sets that are themselves not separated by these separations, we determine conditions under which such a separation system contains a nested subsystem that still separates those sets and is invariant under the automorphisms of the graph. As an application, we show that the \(k\)-blocks -- the maximal vertex sets that cannot be separated by at most \(k\) vertices -- of a graph \(G\) live in distinct parts of a suitable tree-decomposition of \(G\) of adhesion at most \(k\), whose decomposition tree is invariant under the automorphisms of \(G\). This extends recent work of Dunwoody and Kr\"on and, like theirs, generalizes a similar theorem of Tutte for \(k=2\). Under mild additional assumptions, which are necessary, our decompositions can be combined into one overall tree-decomposition that distinguishes, for all \(k\) simultaneously, all the \(k\)-blocks of a finite graph.