pathwidth

abbr: pw

tags: linear variant

equivalent to: pathwidth

providers: ISGCI

Relations

Results

• 2019 The Graph Parameter Hierarchy by Sorge
  • page 11 : treedepth upper bounds pathwidth by a linear function – Lemma 4.27. The treedepth $t$ strictly upper bounds the pathwidth $p$. We have $p \le t$.
• 2015 Linear rank-width and linear clique-width of trees by Adler, Kanté
  • page 3 : pathwidth upper bounds linear rank-width by a linear function – Lemma 5. Any graph $G$ satisfies $\mathrm{lrw}(G) \le \mathrm{pw}(G)$.
• 2010 Comparing 17 graph parameters by Sasák
  • page 16 : graph class tree has unbounded pathwidth – Theorem 2.1
• 2009 Clique-Width is NP-Complete by Fellows, Rosamond, Rotics, Szeider
  • page 8 : pathwidth upper bounds linear clique-width by a linear function – (5) $\mathrm{lin-cwd}(G) \le \mathrm{pwd}(G)+2$.
• 2005 On the relationship between NLC-width and linear NLC-width by Gurski, Wanke
  • page 8 : pathwidth upper bounds linear NLC-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.
• 1998 A partial $k$-arboretum of graphs with bounded treewidth by Bodlaender
  • page 4 : pathwidth upper bounds treewidth by a linear function – Lemma 3. (a) For all graphs $G$, $pathwidth(G) \ge treewidth(G)$. …
  • page 23 : bandwidth upper bounds pathwidth by a linear function – 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 upper bounds pathwidth by a linear function – Theorem 45. For every graph $G$, the pathwidth of $G$ is at most the topological band-width of $G$.
  • page 24 : cutwidth upper bounds pathwidth by a linear function – Theorem 47. For every graph $G$, the pathwidth of $G$ is at most the cutwidth of $G$.
• unknown source
  • pathwidth upper bounds linear rank-width by a computable function
  • distance to linear forest upper bounds pathwidth 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$
  • distance to linear forest upper bounds pathwidth 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$
  • graph class cycles has constant pathwidth – trivially
• https://mathworld.wolfram.com/Pathwidth.html
  • 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.
• assumed
  • pathwidth+maxdegree upper bounds pathwidth by a linear function – by definition
• Comparing Graph Parameters by Schröder
  • page 23 : bounded feedback edge set does not imply bounded pathwidth – Proposition 3.16