The stable hereditary graph class characterization conjecture
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.
Sources & referencesView supporting material
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
Sign in to submit a solution.
No solutions have been posted yet.