Sasak2010

https://hdl.handle.net/1956/4329

@thesis{Sasak2010,
author = {Róbert Sasák},
month = {August},
institution = {University of Bergen},
title = {Comparing 17 graph parameters},
type = {mathesis},
url = {https://hdl.handle.net/1956/4329},
year = {2010},
}

• page 16 : graph class tree has unbounded pathwidth – Theorem 2.1
• page 17 : graph class complete has unbounded treewidth – Theorem 2.2
• page 17 : graph class grid has unbounded treewidth – Theorem 2.4
• page 21 : Jelinek2010 – Theorem 2.14 [12] Rank-width of a grid $\sqrt{n} \times \sqrt{n}$ on $n$ vertices is $\sqrt{n}-1$.
• page 28 : cutwidth $k$ upper bounds maximum degree by $\mathcal O(k)$ – Lemma 2.18. For any graph $G$ and any vertex $v \in V(G), cutw(g) \ge \lceil \frac{deg(v)}2 \rceil$.
• page 30 : carving-width $k$ upper bounds maximum degree by $\mathcal O(k)$ – Lemma 2.20 Carving-width of a graph $G$ is at least $\Delta(G)$ where $\Delta(G)$ is the maximum degree of a graph $G$.
• page 30 : graph class star has unbounded carving-width – Corollary 2.21 Carving-width of a star is $n-1$.
• page 30 : path upper bounds carving-width by a constant – … path with carving-width 2.
• page 32 : graph class grid has unbounded treedepth – Corollary 2.24 Tree-depth of a grid is at least $\lceil \log_2(n+1)\rceil$.
• page 38 : cutwidth $k$ upper bounds carving-width by $\mathcal O(k)$ – Theorem 4.3 (carw $\prec$ cutw) Carving-width is bounded by cut-width.
• page 49 : carving-width $k$ upper bounds treewidth by $\mathcal O(k)$ – Theorem 5.5 (tw $\prec$ carw) Tree-width is bounded by carving-width.