pathwidth+maxdegree

• Bodlaender1998
  • page 24 : pathwidth+maxdegree upper bounds cutwidth by a linear function – Theorem 49.
  • page 24 : cutwidth upper bounds pathwidth+maxdegree by a linear function – Theorem 49.
• assumed
  • pathwidth+maxdegree upper bounds pathwidth by a linear function – by definition
  • pathwidth+maxdegree upper bounds maximum degree by a linear function – by definition