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

DOI10.1007/978-3-319-12340-0_1zbMATH Open1409.05045arXiv1406.3798OpenAlexW59238524MaRDI QIDQ2945175FDOQ2945175

Authors: Reinhard Diestel, Sang-Il Oum 

Publication date: 9 September 2015

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

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]

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

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

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)

Cites Work

• Graph theory
• Graph minors. X: Obstructions to tree-decomposition
• Graph searching and a min-max theorem for tree-width
• Title not available (Why is that?)
• Call routing and the ratcatcher
• Approximating clique-width and branch-width
• Quickly excluding a forest
• Matroid tree-width
• Addendum to matroid tree-width
• Obstructions to branch-decomposition of matroids
• Submodular partition functions

Cited In (16)

• 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
• Title not available (Why is that?)
• 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
• On the block number of graphs
• Tangle and ultrafilter: game theoretical interpretation
• A unified interpretation of several combinatorial dualities
• Refining a tree-decomposition which distinguishes tangles

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)