Unifying duality theorems for width parameters in graphs and matroids (extended abstract)

DOI10.1007/978-3-319-12340-0_1MaRDI QIDQ2945175zbMATH OpenOpenAlexFDO

Authors Reinhard Diestel, Sang-Il Oum

Publication date 9 September 2015

Published in Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1406.3798

zbMATH Keywords

general duality theorem

Mathematics Subject Classification ID

Combinatorial aspects of matroids and geometric lattices (05B35) Distance in graphs (05C12) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: We prove a general duality theorem for tangle-like dense objects in combinatorial structures such as graphs and matroids. This paper continues, and assumes familiarity with, the theory developed in [6]

Recommendations

• Tangle-tree duality: in graphs, matroids and beyond
• Tangle-tree duality in abstract separation systems
• Submodular partition functions
• Duality theorems for blocks and tangles in graphs
• Wei-type duality theorems for matroids

Cites work

• scientific article; zbMATH DE number 420868 (Why is no real title available?)
• Addendum to matroid tree-width
• Approximating clique-width and branch-width
• Call routing and the ratcatcher
• Graph minors. X: Obstructions to tree-decomposition
• Graph searching and a min-max theorem for tree-width
• Graph theory
• Matroid tree-width
• Obstructions to branch-decomposition of matroids
• Quickly excluding a forest
• Submodular partition functions

Cited in

(16)

• Refining a tree-decomposition which distinguishes tangles
• Tangle and Maximal Ideal
• Directed path-decompositions
• On self-duality of branchwidth in graphs of bounded genus
• Partitions versus sets: a case of duality
• Submodular partition functions
• Duality theorems for blocks and tangles in graphs
• scientific article; zbMATH DE number 7561682 (Why is no real title available?)
• Tangles and Hierarchical Clustering
• Dualities in graphs and digraphs
• Rank-width: algorithmic and structural results
• Tangle-tree duality: in graphs, matroids and beyond
• Ends and tangles
• Tangle and ultrafilter: game theoretical interpretation
• On the block number of graphs
• A unified interpretation of several combinatorial dualities

This page was built for publication: Unifying duality theorems for width parameters in graphs and matroids (extended abstract)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2945175)