Minimal-class conjecture for shrub-depth and rank-depth

Let X\mathcal X be a hereditary graph class. A hereditary class is minimal of unbounded shrub-depth and rank-depth if both parameters are unbounded in it, while they are not simultaneously unbounded in any proper hereditary subclass.

Minimal-class conjecture for shrub-depth and rank-depth. Shrub-depth and rank-depth are unbounded in X\mathcal X if and only if X\mathcal X contains a minimal hereditary class of unbounded shrub-depth and rank-depth. The set of minimal classes is infinite and consists of all classes of folded linear forests, together with the classes of chain graphs, complements of chain graphs, and threshold graphs.

The conjecture proposes a complete list of the minimal hereditary obstructions responsible for simultaneous unbounded shrub-depth and rank-depth.

Sources & referencesView supporting material

Primary source

Bogdan Alecu, Vadim Lozin and Dmitriy Malyshev, “Critical properties of bipartite permutation graphs”, arXiv:2010.14467 (2020).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.