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.
Cited by top-tier papers10
- First-Order Model Checking on Structurally Sparse Graph ClassesJan Dreier, Nikolas Mählmann, Sebastian SiebertzSTOC 2023 · 13 citations
- Randomized communication and implicit graph representationsNathaniel Harms, Sebastian Wild, Viktor ZamaraevSTOC 2022 · 11 citations
- Flip-width: Cops and Robber on dense graphsSzymon TorunczykFOCS 2023 · 9 citations
- Treelike Decompositions for Transductions of Sparse GraphsJan Dreier, Jakub Gajarský, Sandra Kiefer, Michal Pilipczuk et al.LICS 2022 · 8 citations
- Efficient Reversal of Transductions of Sparse Graph ClassesJan Dreier, Jakub Gajarský, Michal PilipczukSTOC 2026 · 5 citations
Builds on3
- Twin-width I: tractable FO model checkingÉdouard Bonnet, Eun Jung Kim, Stéphan Thomassé, Rémi WatrigantFOCS 2020 · 82 citations
- Twin-width II: small classesÉdouard Bonnet, Colin Geniet, Eun Jung Kim, Stéphan Thomassé et al.SODA 2021 · 61 citations
- Rankwidth meets stabilityJaroslav Nesetril, Patrice Ossona de Mendez, Michal Pilipczuk, Roman Rabinovich et al.SODA 2021 · 23 citations
Related papers
- Linear rankwidth meets stabilityJaroslav Nesetril, Roman Rabinovich, Patrice Ossona de Mendez, Sebastian SiebertzSODA 2020
- Existential Positive Transductions of Sparse GraphsNikolas Mählmann, Sebastian SiebertzLICS 2026
- Factoring Pattern-Free Permutations into Separable onesEdouard Bonnet, Romain Bourneuf, Colin Geniet, Stéphan ThomasséSODA 2024 · 2 citations
- 3D-grids are not transducible from planar graphsJakub Gajarský, Michal Pilipczuk, Filip PokrývkaLICS 2025 · 2 citations
- Flip-Breakability: A Combinatorial Dichotomy for Monadically Dependent Graph ClassesJan Dreier, Nikolas Mählmann, Szymon TorunczykSTOC 2024 · 8 citations
