Stable graphs of bounded twin-width

07/08/2021
by   Jakub Gajarsky, et al.
0

We prove that every class of graphs 𝒞 that is monadically stable and has bounded twin-width can be transduced from some class with bounded sparse twin-width. This generalizes analogous results for classes of bounded linear cliquewidth and of bounded cliquewidth. It also implies that monadically stable classes of bounded twin-widthare linearly χ-bounded.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset