Connected Tree-Width

Link:
Autor/in:
Erscheinungsjahr:
2018
Medientyp:
Text
Beschreibung:
  • The connected tree-width of a graph is the minimum width of a tree-decomposition whose parts induce connected subgraphs. Long cycles are examples of graphs that have small tree-width but large connected tree-width. We show that a graph has small connected tree-width if and only if it has small tree-width and contains no long geodesic cycle. We further prove a connected analogue of the duality theorem for tree-width: a finite graph has small connected tree-width if and only if it has no bramble whose connected covers are all large. Both these results are qualitative: the bounds are good but not tight. We show that graphs of connected tree-width k are k-hyperbolic, which is tight, and that graphs of tree-width k whose geodesic cycles all have length at most ℓ are ⌊3/2l(k-1)⌋-hyperbolic. The existence of such a function h(k, ℓ) had been conjectured by Sullivan.
Lizenz:
  • info:eu-repo/semantics/restrictedAccess
Quellsystem:
Forschungsinformationssystem der UHH

Interne Metadaten
Quelldatensatz
oai:www.edit.fis.uni-hamburg.de:publications/cc5f1502-7057-48c8-9dd6-76624d17b9f5