Uniqueness and minimal obstructions for tree-depth

A kk-ranking of a graph GG is a labeling of the vertices of GG with values from {1,…,k}{1,…,k} such that any path joining two vertices with the same label contains a vertex having a higher label. The tree-depth of GG is the smallest value of kk for which a kk-ranking of GG exists. The graph GG is kk-critical if it has tree-depth kk and every proper minor of GG has smaller tree-depth.We establish partial results in support of two conjectures about the order and maximum degree of kk-critical graphs. As part of these results, we define a graph GG to be 1-unique   if for every vertex vv in GG, there exists an optimal ranking of GG in which vv is the unique vertex with label 1. We show that several classes of kk-critical graphs are 1-unique, and we conjecture that the property holds for all kk-critical graphs. Generalizing a previously known construction for trees, we exhibit an inductive construction that uses 1-unique kk-critical graphs to generate large classes of critical graphs having a given tree-depth.