pathwidth+maxdegree

• 1998 Bodlaender1998
  • page 24 : pathwidth+maxdegree $k$ upper bounds cutwidth by $\mathcal O(k)$ – Theorem 49.
  • page 24 : cutwidth $k$ upper bounds pathwidth+maxdegree by $\mathcal O(k)$ – Theorem 49.
• unknown
  • pathwidth+maxdegree $k$ upper bounds pathwidth by $\mathcal O(k)$ – by definition
  • pathwidth+maxdegree $k$ upper bounds maximum degree by $\mathcal O(k)$ – by definition