Duality theorems for blocks and tangles in graphs

Link:
Autor/in:
Erscheinungsjahr:
2017
Medientyp:
Text
Schlagworte:
  • Algorithms
  • Graphic methods
  • Tree decomposition
  • Graph In Graph Theory
  • Coloring
  • Graphic Methods
  • Algorithms
  • Graphic methods
  • Tree decomposition
  • Graph In Graph Theory
  • Coloring
  • Graphic Methods
Beschreibung:
  • We prove a duality theorem applicable to a wide range of specializations, as well as to some generalizations, of tangles in graphs. It generalizes the classical tangle duality theorem of Robertson and Seymour, which says that every graph has either a large-order tangle or a certain low-width tree-decomposition witnessing that it cannot have such a tangle. Our result also yields duality theorems for profiles and for k-blocks. This solves a problem studied, but not solved, by Diestel and Oum and answers an earlier question of Carmesin, Diestel, Hamann, and Hundertmark.
Lizenz:
  • info:eu-repo/semantics/restrictedAccess
Quellsystem:
Forschungsinformationssystem der UHH

Interne Metadaten
Quelldatensatz
oai:www.edit.fis.uni-hamburg.de:publications/45fe7f7b-6709-4224-aba9-4cb4aa0cfc97