Tree-depth
, the minimum height of a Trémaux tree for a supergraph of
This invariant and its close relatives have gone under many different names in the literature, including vertex ranking number, ordered chromatic number, and minimum elimination tree height; it is also closely related to the cycle rank of directed graphs and the star height of regular languages.
connects a pair of nodes that have an ancestor-descendant relationship to each other in
is connected, this forest must be a single tree; it need not be a subgraph of
forms a trivially perfect graph, and the height of
Thus, the tree-depth may alternatively be defined as the size of the largest clique in a trivially perfect supergraph of
, mirroring the definition of treewidth as one less than the size of the largest clique in a chordal supergraph of
Tree-depth may also be defined using a form of graph coloring.
The robber has one pebble he can move along the edges of the given graph.
The cop cannot move a pebble after it has been placed on the graph.
The robber can then move his pebble along edges, but not through occupied vertices.
The tree-depth of the given graph is the minimum number of pebbles needed by the cop to guarantee a win.
vertices, the cop uses a binary search strategy, which guarantees that at most
The tree-depth of a complete graph equals its number of vertices.
for which every pair of vertices are in an ancestor-descendant relationship is a single path.
Similarly, the tree-depth of a complete bipartite graph
bound may be constructed by forming a path for the smaller side of the bipartition, with each vertex on the larger side of the bipartition forming a leaf in
By recursively partitioning each of these two subforests, one can easily derive a logarithmic upper bound on the tree-depth.
The same technique, applied to a tree decomposition of a graph, shows that, if the treewidth of an
The typical graphs with large treedepth and small treewidth are the perfect binary trees and the paths.
), the relation of being an induced subgraph forms a well-quasi-ordering.
[13] The basic idea of the proof that this relation is a well-quasi-ordering is to use induction on
(formed by deleting the roots of the trees in the height-
forest) and Higman's lemma can be used together with the induction hypothesis to show that these sequences are well-quasi-ordered.
Well-quasi-ordering implies that any property of graphs that is monotonic with respect to induced subgraphs has finitely many forbidden induced subgraphs, and therefore may be tested in polynomial time on graphs of bounded tree-depth.
themselves also have a finite set of forbidden induced subgraphs.
[18] For undirected trees, tree-depth can be computed in linear time.
, based on the fact that tree-depth is always within a logarithmic factor of the treewidth of a graph.
in this algorithm can be made linear, by the following method: compute a depth first search tree, and test whether this tree's depth is greater than
If not, the shallow depth first search tree can be used to construct a tree decomposition with bounded width, and standard dynamic programming techniques for graphs of bounded treewidth can be used to compute the depth in linear time.
