# Graphclass: bounded treewidth

Definition:

A tree decomposition of a graph G=(V,E) is a pair ({Xi | i in I}, T = (I, F)) with {Xi | i in I} a family of subsets of V, one for each node in T, and T a tree such that

• the union of all Xi, i in I equals V.
• for all edges (v,w) in E, there exists i in I, such that v in Xi and w in Xi.
• for all v in V: the set of nodes {i in I | v in Xi} forms a subtree of T
The width of the tree decomposition is max |Xi | - 1.
The treewidth of a graph is the minimum width over all possible tree decompositions of the graph.
A graph is of bounded treewidth if its treewidth is at most a given constant k.

[119] [1411]

[+]Details

## Inclusions

The map shows the inclusions between the current class and a fixed set of landmark classes. Minimal/maximal is with respect to the contents of ISGCI. Only references for direct inclusions are given. Where no reference is given, check equivalent classes or use the Java application. To check relations other than inclusion (e.g. disjointness) use the Java application, as well.

[+]Details

[+]Details

[+]Details

## Problems

3-Colourability Linear [+]Details
Clique Linear [+]Details
Clique cover Polynomial [+]Details
Cliquewidth Bounded [+]Details
Cliquewidth expression Polynomial [+]Details
Colourability Polynomial [+]Details
Cutwidth Linear [+]Details
Domination Linear [+]Details
Feedback vertex set Polynomial [+]Details
Hamiltonian cycle Linear [+]Details
Hamiltonian path Polynomial [+]Details
Independent set Linear [+]Details
Recognition Linear [+]Details
Treewidth Linear [+]Details
Weighted clique Linear [+]Details
Weighted feedback vertex set Polynomial [+]Details
Weighted independent set Linear [+]Details