carving-width

equivalent to: carving-width

providers: ISGCI

Relations

Results

• 2013 Characterizing graphs of small carving-width by Belmonte, van ’t Hof, Kamiński, Paulusma, Thilikos
  • carving-width upper bounds maximum degree by a linear function – Observation 1. Let $G$ be a graph. Then $cw(G) \ge \Delta(G)$.
• 2010 Comparing 17 graph parameters by Sasák
  • 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.
• https://link.springer.com/article/10.1007/bf01215352
  • 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$.
• https://en.wikipedia.org/wiki/Carving_width
  • 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.