# Parameter: carvingwidth

Definition:

Consider a decomposition $(T,\chi)$ of a graph $G$ where $T$ is a binary tree with $|V(G)|$ leaves and $\chi$ is a bijection mapping the leaves of $T$ to the vertices of $G$. Every edge $e \in E(T)$ of the tree $T$ partitions the vertices of the graph $G$ into two parts $V_e$ and $V \backslash V_e$ according to the leaves of the two connected components in $T - e$. The width of an edge $e$ of the tree is the number of edges of a graph $G$ that have exactly one endpoint in $V_e$ and another endpoint in $V \backslash V_e$. The width of the decomposition $(T,\chi)$ is the largest width over all edges of the tree $T$. The carvingwidth of a graph is the minimum width over all decompositions as above.

## Relations

Minimal/maximal is with respect to the contents of ISGCI. Only references for direct bounds are given. Where no reference is given, check equivalent parameters.

[+]Details

[+]Details

## Problems

Problems in italics have no summary page and are only listed when ISGCI contains a result for the current parameter.

3-Colourability FPT [+]Details
Clique FPT [+]Details
Clique cover XP [+]Details
Colourability FPT [+]Details
Domination FPT [+]Details
Feedback vertex set FPT [+]Details
Graph isomorphism FPT [+]Details
Hamiltonian cycle FPT [+]Details
Hamiltonian path FPT [+]Details
Independent set FPT [+]Details
Maximum cut FPT [+]Details
Monopolarity Unknown to ISGCI [+]Details
Polarity XP [+]Details
Weighted clique FPT [+]Details
Weighted feedback vertex set FPT [+]Details
Weighted independent dominating set FPT [+]Details
Weighted independent set FPT [+]Details