Bounding connected tree-width

Link:
Autor/in:
Erscheinungsjahr:
2016
Medientyp:
Text
Schlagworte:
  • Graph in graph theory
  • Game
  • Capture time
  • Graph In Graph Theory
  • Coloring
  • Graphic Methods
  • Graph in graph theory
  • Game
  • Capture time
  • Graph In Graph Theory
  • Coloring
  • Graphic Methods
Beschreibung:
  • Diestel and Muller showed that the connected tree-width of a graph G, i.e., the minimum width of any tree-decomposition with connected parts, can be bounded in terms of the tree-width of G and the largest length of a geodesic cycle in G. We improve their bound to one that is of the correct order of magnitude. Finally, we construct a graph whose connected tree-width exceeds the connected order of any of its brambles. This disproves a conjecture by Diestel and Muller asserting an analogue of tree-width duality.
Lizenz:
  • info:eu-repo/semantics/restrictedAccess
Quellsystem:
Forschungsinformationssystem der UHH

Interne Metadaten
Quelldatensatz
oai:www.edit.fis.uni-hamburg.de:publications/a35afccc-8b76-4b6a-b78d-47e65b103e2b