The order bound conjecture for critical graphs

A graph is critical with tree-depth $k$ if its tree-depth is $k$ and every proper minor has smaller tree-depth. The order of a graph is its number of vertices.

The order bound conjecture. Every critical graph with tree-depth $k$ has at most

$$2^{k-1}$$

vertices.

The conjecture appears in work of Dvořák, Giannopoulou, and Thilikos, where its original form also includes induced-subgraph-critical graphs. The paper establishes partial results toward the bound; the general statement remains open.