Stability characterization for bounded-linear-rankwidth graph classes

Let C\mathscr{C} be a class of graphs with bounded linear rankwidth. A first-order transduction is a graph interpretation obtained using first-order formulas. The class C\mathscr{C} is stable if no first-order formula defines arbitrarily large orders. Linear-rankwidth stability conjecture. The class C\mathscr{C} is included in a first-order transduction of a class D\mathscr{D} with bounded pathwidth if and only if C\mathscr{C} 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

Never refreshed

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.