Stability characterization for bounded-linear-rankwidth graph classes

About 7 years old · traced to

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.

References

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.