# Parameter: tree depth

Definition:

A tree depth decomposition of a graph $G = (V,E)$ is a rooted tree $T$ with the same vertices $V$, such that, for every edge $\{u,v\} \in E$, either $u$ is an ancestor of $v$ or $v$ is an ancestor of $u$ in the tree $T$. The depth of $T$ is the maximum number of vertices on a path from the root to any leaf. The tree depth of a graph $G$ is the minimum depth among all tree depth decompositions.

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