carving-width – A carving can be described as an unrooted binary tree whose leaves are labeled with the vertices of the given graph. Removing any edge from this tree partitions the tree into two subtrees, and correspondingly partitions the vertices of the tree into two clusters. … The width of a carving, defined in this way, is the maximum number of edges that connect two complementary clusters. The carving width of the graph is the minimum width of any hierarchical clustering.
carving-width – Let $V$ be a finite set with $|V| \ge 2$. Two subsets $A,B\subseteq V$ \emph{cross} if $A\cap B$, $A-B$, $B-A$, $V-(A\cup B)$ are all non-empty. A \emph{carving} in $V$ is a set $\mathscr{C}$ of subsets of $V$ such that 1) $\emptyset, V \notin \mathscr{C}$ 2) no two members of $\mathscr{C}$ cross, and 3) $\mathscr{C}$ is maximal subject to (1) and (2). … For $A \subseteq V(G)$, we denote by $\delta(A)$ … the set of all edges with an end in $A$ and an end in $V(G)-A$. For each $e \in E(G)$, let $p(e) \ge 0$ be an integer. For $X \subseteq E(G)$ we denote $\sum_{e \in X}p(e)$ by $p(X)$, and if $|V(G)| \ge 2$ we define the \emph{$p$-carving-width} of $G$ to be the minimum, over all carvings $\mathscr{C}$ in $V(G)$, of the maximum, over all $A \in \mathscr{C}$, of $p(\delta(A))$. … The \emph{carving-width} of $G$ is the $p$-carving-width of $G$ where $p(e)=1$ for every edge $e$.
page 30 : carving-width upper bounds maximum degree by a linear function – Lemma 2.20 Carving-width of a graph $G$ is at least $\Delta(G)$ where $\Delta(G)$ is the maximum degree of a graph $G$.
page 30 : graph class star has unbounded carving-width – Corollary 2.21 Carving-width of a star is $n-1$.
page 30 : graph class path has constant carving-width – … path with carving-width 2.
page 38 : cutwidth upper bounds carving-width by a linear function – Theorem 4.3 (carw $\prec$ cutw) Carving-width is bounded by cut-width.
page 49 : carving-width upper bounds treewidth by a linear function – Theorem 5.5 (tw $\prec$ carw) Tree-width is bounded by carving-width.
