The shrub-depth characterization by vertex-minors
The shrub-depth characterization by vertex-minors
Let 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 is of bounded shrub-depth if, and only if, there exists an integer such that no graph contains a path of length 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
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.