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.
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.
page 16 : treewidth upper bounds branch width by a linear function – (5.1) For any hypergraph $G$, $\max(\beta(G), \gamma(G)) \le \omega(G) + 1 \le \max(\lfloor(3/2)\beta(G)\rfloor, \gamma(G), 1)$.
page 16 : branch width upper bounds treewidth by a linear function – (5.1) For any hypergraph $G$, $\max(\beta(G), \gamma(G)) \le \omega(G) + 1 \le \max(\lfloor(3/2)\beta(G)\rfloor, \gamma(G), 1)$.
page 18 : treewidth upper bounds clique-width by an exponential function – We will prove that for every undirected graph $G$, $cwd(G) \le 2^{twd(G)+1}+1$ …
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 4 : treewidth upper bounds thickness by a linear function – Proposition 1. The maximum thickness of a graph in $\mathcal T_k$ (ed: $k$-tree) is $\lceil k/2 \rceil$; …
page 5 : treewidth upper bounds arboricity by a linear function – Proposition 2. The maximum arboricity of a graph in $\mathcal T_k$ (ed: $k$-tree) is $k$; …
page 5 : treewidth upper bounds outerthickness by a linear function – Proposition 3. The maximum outerthickness of a graph in $\mathcal T_k$ (ed: $k$-tree) is $k$; …
page 6 : treewidth upper bounds star-arboricity by a linear function – Proposition 4. The maximum star-arboricity of a graph in $\mathcal T_k$ (ed: $k$-tree) is $k+1$; …
page 8 : treewidth upper bounds book thickness by a linear function – 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 4 : pathwidth upper bounds treewidth by a linear function – Lemma 3. (a) For all graphs $G$, $pathwidth(G) \ge treewidth(G)$. …
page 34 : graph class outerplanar has constant treewidth – 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 upper bounds minimum degree by a linear function – Lemma 90 (Scheffler [94]). Every graph of treewidth at most $k$ contains a vertex of degree at most $k$.
page 6 : treewidth upper bounds NLC-width by an exponential function – Theorem 2.5. For each partial $k$-tree $G$ there is a $(2^{k+1}-1)$-NLC tree $J$ with $G=unlab(J)$.
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$.
distance to outerplanar upper bounds treewidth by a linear function – 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$
page 8 : treewidth upper bounds NLCT-width by a computable function – 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.
