The shrubdepth characterization by paths
The shrubdepth characterization by paths
Let be a class of graphs, let denote the class of paths, and let 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 has bounded shrubdepth if and only if
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
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.