The shrub-depth characterization by vertex-minors
Statement
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.
Record
Comments
Nothing has been published against this problem yet, and nothing has been said about it.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.