Tree-depth

In graph theory, the tree-depth of a connected undirected graph is a numerical invariant of , 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. Intuitively, where the treewidth of a graph measures how far it is from being a tree, this parameter measures how far a graph is from being a star. The tree-depth of a graph may be defined as the minimum height of a forest with the property that every edge of connects a pair of nodes that have an ancestor-descendant relationship to each other in . If is connected, this forest must be a single tree; it need not be a subgraph of , but if it is, it is a Trémaux tree for . The set of ancestor-descendant pairs in forms a trivially perfect graph, and the height of 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 , mirroring the definition of treewidth as one less than the size of the largest clique in a chordal supergraph of . Another definition is the following: where is the set of vertices of and the are the connected components of . This definition mirrors the definition of cycle rank of directed graphs, which uses strong connectivity and strongly connected components in place of undirected connectivity and connected components. Tree-depth may also be defined using a form of graph coloring. A centered coloring of a graph is a coloring of its vertices with the property that every connected induced subgraph has a color that appears exactly once. Then, the tree-depth is the minimum number of colors in a centered coloring of the given graph. If is a forest of height with the property that every edge of connects an ancestor and a descendant in , then a centered coloring of using colors may be obtained by coloring each vertex by its distance from the root of its tree in .