cutwidth

tags: vertex order

equivalent to: cutwidth, pathwidth+maxdegree

providers: ISGCI

Relations

Results

• 2010 Comparing 17 graph parameters by Sasák
  • page 28 : cutwidth upper bounds maximum degree by a linear function – Lemma 2.18. For any graph $G$ and any vertex $v \in V(G), cutw(g) \ge \lceil \frac{deg(v)}2 \rceil$.
  • page 38 : cutwidth upper bounds carving-width by a linear function – Theorem 4.3 (carw $\prec$ cutw) Carving-width is bounded by cut-width.
• 1998 A partial $k$-arboretum of graphs with bounded treewidth by Bodlaender
  • page 22 : cutwidth – Let $G=(V,E)$ be a graph, and let $f\colon V\to {1,2,\dots,n}$ be a linear ordering of $G$. … 2. The \emph{cutwidth} of $f$ is $\max_{1\le i\le n} |{(u,v)\in E \mid f(u) \le i < f(v) }|$. … [cutwidth] of a graph $G$ is the minimum [cutwidth] … over all possible linear orderings 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$.
  • 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.
• unknown source
  • bandwidth upper and lower bounds cutwidth by a polynomial function – Any bandwidth bound cutwidth quadratically. An example where this happens is $(P_n)^k$ which has bandwidth $k$ and cutwidth $O(k^2)$; both seem to be optimal.
  • bounded components upper bounds cutwidth by a polynomial function – By greedily placing one component after another.