Tree-depth

In graph theory, the tree-depth of a connected undirected graph G is a numerical invariant of G, the minimum height of a Trémaux tree for a supergraph of G. 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. Intuitively, where the treewidth graph width parameter measures how far a graph is from being a tree, this parameter measures how far a graph is from being a star.

The tree-depth of a graph G may be defined as the minimum height of a forest F with the property that every edge of G connects a pair of nodes that have an ancestor-descendant relationship to each other in F. If G is connected, this forest must be a single tree; it need not be a subgraph of G, but if it is, it is a Trémaux tree for G.

The set of ancestor-descendant pairs in F forms a trivially perfect graph, and the height of F is the size of the largest clique in this graph. Thus, the tree-depth may alternatively be defined as the size of the largest clique in a trivially perfect supergraph of G, mirroring the definition of treewidth as one less than the size of the largest clique in a chordal supergraph of G.

...
Wikipedia