The shrubdepth characterization by paths

Let C\mathcal{C} be a class of graphs, let P\mathcal{P} denote the class of paths, and let FO\sqsupseteq_\mathrm{FO} denote the first-order transduction quasiorder. A graph class has bounded shrubdepth when it is first-order interpretable in some fixed finite-height rooted tree class. The shrubdepth characterization by paths. A class C\mathcal{C} has bounded shrubdepth if and only if

C̸FOP.\mathcal{C}\not\sqsupseteq_\mathrm{FO}\mathcal{P}.

This conjecture characterizes bounded shrubdepth by excluding the class of paths as a first-order transduction target. The surrounding discussion presents it as one of the difficult structural questions about the first-order transduction quasiorder; its resolution status is not specified in the source.

Sources & referencesView supporting material

Primary source

Jaroslav Nesetril, Patrice Ossona de Mendez and Sebastian Siebertz, “Structural properties of the first-order transduction quasiorder”, arXiv:2010.02607 (2021).

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.