Lune

LICS2022Top-tier venue

Stable graphs of bounded twin-width

Jakub Gajarský, Michal Pilipczuk, Szymon Torunczyk

2022Year
16Citations
10Top-tier citations

Abstract

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 [Nešetřil et al. 2021b] and of bounded cliquewidth [Nešetřil et al. 2021a]. It also implies that monadically stable classes of bounded twin-width are linearly χ-bounded.

Ask about this paper

Your agent reads all of it.

Lune indexed this paper to the last equation, along with the top-tier papers that cite it. Ask a question and the answer quotes them.

Questions to start from

Your agent calls

Luneget_paper_fulltext

Ask in Lune

Free to start. No credit card required.

Cited by top-tier papers10

Ask how each one uses it

Builds on3

Related papers

Dusk over the sea between two cliffs drawn in fine vertical lines