page 8 : pathwidth $k$ upper bounds linear NLC-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 4 : pathwidth $k$ upper bounds treewidth by $\mathcal O(k)$ – Lemma 3. (a) For all graphs $G$, $pathwidth(G) \ge treewidth(G)$. …
page 23 : bandwidth $k$ upper bounds pathwidth by $\mathcal O(k)$ – Theorem 44. For every graph $G$, the pathwidth of $G$ is at most the bandwidth of $G$, … Proof. Let $f \colon V\to {1,\dots,n}$ be a linear ordering of $G$ with bandwidth $k$. Then $(X_1,\dots,X_{n-k})$ with $X_i={f^{-1}(i), f^{-1}(i+1), \dots, f^{-1}(i+k)}$ is a path decomposition of $G$ with pathwidth $k$. …
page 23 : topological bandwidth $k$ upper bounds pathwidth by $\mathcal O(k)$ – Theorem 45. For every graph $G$, the pathwidth of $G$ is at most the topological band-width of $G$.
page 24 : cutwidth $k$ upper bounds pathwidth by $\mathcal O(k)$ – Theorem 47. For every graph $G$, the pathwidth of $G$ is at most the cutwidth of $G$.
pathwidth – The pathwidth of a graph $G$, also called the interval thickness, vertex separation number, and node searching number, is one less than the size of the largest set in a path decomposition G.
distance to linear forest $k$ upper bounds pathwidth 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$
distance to linear forest $k$ upper bounds pathwidth 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$
