The shrub-depth characterization by vertex-minors

Let C\mathcal{C} be a class of graphs. A graph is of bounded shrub-depth if its shrub-depth is bounded by some fixed integer.

Shrub-depth characterization conjecture. The class C\mathcal{C} is of bounded shrub-depth if, and only if, there exists an integer tt such that no graph GCG\in\mathcal{C} contains a path of length tt as a vertex-minor.

This asks whether excluding a fixed path as a vertex-minor exactly characterizes classes of graphs of bounded shrub-depth. The surrounding discussion presents it as a natural question following the construction of cographs containing arbitrarily long paths as pivot-minors; its resolution is not specified in the source.

Sources & referencesView supporting material

Primary source

Petr Hliněný, O-joung Kwon, Jan Obdržálek and Sebastian Ordyniak, “Tree-depth and Vertex-minors”, arXiv:1403.7024 (2014).

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.