Parameters tied to treewidth

Daniel J. Harvey, David R. Wood

Research output: Contribution to journalArticleResearchpeer-review

51 Citations (Scopus)

Abstract

Treewidth is a graph parameter of fundamental importance to algorithmic and structural graph theory. This article surveys several graph parameters tied to treewidth, including separation number, tangle number, well-linked number, and Cartesian tree product number. We review many results in the literature showing these parameters are tied to treewidth. In a number of cases we also improve known bounds, provide simpler proofs, and show that the inequalities presented are tight.

Original languageEnglish
Pages (from-to)364-385
Number of pages22
JournalJournal of Graph Theory
Volume84
Issue number4
DOIs
Publication statusPublished - Apr 2017

Keywords

  • Branchwidth
  • Graph parameters
  • Separators
  • Treewidth

Cite this