Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
Tree-depth
Summary
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 .
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.