# Parameter: branchwidth

Definition:

A branch decomposition of a graph $G$ is a pair $(T,\chi)$, where $T$ is a binary tree and $\chi$ is a bijection, mapping leaves of $T$ to edges of $G$. Any edge $\{u, v\}$ of the tree divides the tree into two components and divides the set of edges of $G$ into two parts $X, E \backslash X$, consisting of edges mapped to the leaves of each component. The width of the edge $\{u,v\}$ is the number of vertices of $G$ that is incident both with an edge in $X$ and with an edge in $E \backslash X$. The width of the decomposition $(T,\chi)$ is the maximum width of its edges. The branchwidth of the graph $G$ is the minimum width over all branch-decompositions of $G$.

[+]Details

## 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