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