Stability characterization for bounded-linear-rankwidth graph classes
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.
Sources & referencesView supporting material
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
Sign in to submit a solution.
No solutions have been posted yet.