ProbXiv
Explorersign in
Problem archiveProblem record

Statement

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 G∈CG\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.

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 in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.