Projects per year
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 language | English |
---|---|
Pages (from-to) | 364-385 |
Number of pages | 22 |
Journal | Journal of Graph Theory |
Volume | 84 |
Issue number | 4 |
DOIs | |
Publication status | Published - Apr 2017 |
Keywords
- Branchwidth
- Graph parameters
- Separators
- Treewidth
Projects
- 3 Finished
-
Graph colouring via entropy compression
Australian Research Council (ARC)
2/01/14 → 31/12/17
Project: Research
-
Hadwiger's graph colouring conjecture
Wood, D. & Zhou, S.
Australian Research Council (ARC), University of Melbourne
1/01/12 → 30/04/15
Project: Research
-
The Structure and Geometry of Graphs
Australian Research Council (ARC)
1/01/08 → 31/12/13
Project: Research