The stable hereditary graph class characterization conjecture
Let be a hereditary class of graphs, meaning that every induced subgraph of every graph in also belongs to . A low shrubdepth decomposition with parts is a decomposition of an -vertex graph into a subpolynomial number of parts such that every fixed-size collection of parts induces a graph from a class of bounded shrubdepth. The properties under consideration are first-order transducibility from nowhere dense classes, admitting such decompositions, monadic stability, and stability.
Stable hereditary graph class characterization conjecture. The following properties are equivalent:
- is a first-order transduction of a nowhere dense class;
- admits low shrubdepth decompositions with parts;
- is monadically stable;
- is stable.
This is proposed as a strengthening of the monadic stability characterization conjecture. The source gives no resolution evidence, so the equivalence remains open.
References
Primary source
Samuel Braunfeld, Jaroslav Nešetřil, Patrice Ossona de Mendez and Sebastian Siebertz, “Decomposition horizons and a characterization of stable hereditary classes of graphs”, arXiv:2209.11229 (2024).
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
No solutions have been posted yet.