page 263 : bounded twin-cover number does not imply bounded treewidth – There exists graphs with arbitrarily large twin-cover and bounded tree-width and vice-versa.
page 263 : bounded treewidth does not imply bounded twin-cover number – There exists graphs with arbitrarily large twin-cover and bounded tree-width and vice-versa.
page 4 : treewidth $k$ upper bounds thickness by $\mathcal O(k)$ – Proposition 1. The maximum thickness of a graph in $\mathcal T_k$ (ed: $k$-tree) is $\lceil k/2 \rceil$; …
page 5 : treewidth $k$ upper bounds arboricity by $\mathcal O(k)$ – Proposition 2. The maximum arboricity of a graph in $\mathcal T_k$ (ed: $k$-tree) is $k$; …
page 5 : treewidth $k$ upper bounds outerthickness by $\mathcal O(k)$ – Proposition 3. The maximum outerthickness of a graph in $\mathcal T_k$ (ed: $k$-tree) is $k$; …
page 6 : treewidth $k$ upper bounds star-arboricity by $\mathcal O(k)$ – Proposition 4. The maximum star-arboricity of a graph in $\mathcal T_k$ (ed: $k$-tree) is $k+1$; …
page 8 : treewidth $k$ upper bounds book thickness by $\mathcal O(k)$ – The maximum book thickness … of a graph $\mathcal T_k$ (ed: $k$-tree) satisfy … $=k$ for $k \le 2$, $=k+1$ for $k \ge 3$.
page 8 : treewidth $k$ upper bounds NLCT-width by $f(k)$ – The results of [23] imply that each graph class of bounded path-width has bounded linear NLC-width and that each graph class of bounded tree-width has bounded NLCT-width.
page 18 : treewidth $k$ upper bounds clique-width by $2^{\mathcal O(k)}$ – We will prove that for every undirected graph $G$, $cwd(G) \le 2^{twd(G)+1}+1$ …
page 4 : pathwidth $k$ upper bounds treewidth by $\mathcal O(k)$ – Lemma 3. (a) For all graphs $G$, $pathwidth(G) \ge treewidth(G)$. …
page 34 : outerplanar upper bounds treewidth by a constant – Lemma 78. Every outerplanar graph $G=(V,E)$ has treewidth at most 2.
page 37 : graph class grid has unbounded treewidth – Lemma 88. The treewidth of an $n \times n$ grid graph … is at least $n$.
page 38 : treewidth $k$ upper bounds minimum degree by $\mathcal O(k)$ – Lemma 90 (Scheffler [94]). Every graph of treewidth at most $k$ contains a vertex of degree at most $k$.
page 6 : treewidth $k$ upper bounds NLC-width by $2^{\mathcal O(k)}$ – Theorem 2.5. For each partial $k$-tree $G$ there is a $(2^{k+1}-1)$-NLC tree $J$ with $G=unlab(J)$.
page 4 : graph class complete has unbounded treewidth – Lemma 3.1 (“clique containment lemma”). Let $({X_i\mid u\in I},T=(I,F))$ be a tree-decomposition of $G=(V,E)$ and let $W \subseteq V$ be a clique in $G$. Then there exists $i \in I$ with $W \subseteq X_i$.
page 4 : graph class bipartite has unbounded treewidth – Lemma 3.2 (“complete bipartite subgraph containment lemma”).
page 1 : treewidth – A \emph{tree-decomposition} of $G$ is a family $(X_i \colon i\in I)$ of subsets of $V(G)$, together with a tree $T$ with $V(T)=I$, with the following properties. (W1) $\bigcup(X_i \colon i \in I)=V(G)$. (W2) Every edge of $G$ has both its ends in some $X_i$ ($i \in I$). (W3) For $i,j,k \in I$, if $j$ lies on the path of $T$ from $i$ to $k$ then $X_i \cap X_k \subseteq X_j$. The \emph{width} of the tree-decomposition is $\max(|X_i|-1 \colon i \in I)$. The tree-width of $G$ is the minimum $w \ge 0$ such that $G$ has a tree-decomposition of width $\le w$.
page 1 : treewidth – Equivalently, the tree-width of $G$ is the minimum $w \ge 0$ such that $G$ is a subgraph of a ``chordal’’ graph with all cliques of size at most $w + 1$.
treewidth – Very roughly, treewidth captures how similar a graph is to a tree. There are many ways to define ``tree-likeness’’ of a graph; … it appears that the approach most useful from algorithmic and graph theoretical perspectives, is to view tree-likeness of a graph $G$ as the existence of a structural decomposition of $G$ into pieces of bounded size that are connected in a tree-like fashion. This intuitive concept is formalized via the notions of a tree decomposition and the treewidth of a graph; the latter is a quantitative measure of how good a tree decomposition we can possibly obtain.
distance to outerplanar $k$ upper bounds treewidth by $\mathcal O(k)$ – After removal of $k$ vertices the remaining class has a bounded width $w$. So by including the removed vertices in every bag, we can achieve decomposition of width $w+k$