Minimal-class conjecture for shrub-depth and rank-depth
Minimal-class conjecture for shrub-depth and rank-depth
Let 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 if and only if 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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.