Stability characterization for bounded-linear-rankwidth graph classes
Let be a class of graphs with bounded linear rankwidth. A first-order transduction is a graph interpretation obtained using first-order formulas. The class is stable if no first-order formula defines arbitrarily large orders. Linear-rankwidth stability conjecture. The class is included in a first-order transduction of a class with bounded pathwidth if and only if is stable.
This conjecture is the linear analogue of the rankwidth characterization, relating stability to first-order descriptions by classes of bounded pathwidth. The supplied text gives no resolution status.
References
Primary source
Jaroslav Nesetril, Patrice Ossona de Mendez, Roman Rabinovich and Sebastian Siebertz, “Linear rankwidth meets stability”, arXiv:1911.07748 (2019).
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.