Stable graphs of bounded twin-width
Jakub Gajarský, Michal Pilipczuk, Szymon Torunczyk
2022年份
16被引次数
10顶会引用
摘要
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.
问问这篇 Paper
智能体会读完全文。
Lune 把这篇 Paper 索引到了每一个公式,引用它的顶会 Paper 也一样。你提问,回答直接引用原文。
引用它的顶会 Paper10
- First-Order Model Checking on Structurally Sparse Graph ClassesJan Dreier, Nikolas Mählmann, Sebastian SiebertzSTOC 2023 · 被引用 13 次
- Randomized communication and implicit graph representationsNathaniel Harms, Sebastian Wild, Viktor ZamaraevSTOC 2022 · 被引用 11 次
- Flip-width: Cops and Robber on dense graphsSzymon TorunczykFOCS 2023 · 被引用 9 次
- Treelike Decompositions for Transductions of Sparse GraphsJan Dreier, Jakub Gajarský, Sandra Kiefer, Michal Pilipczuk 等LICS 2022 · 被引用 8 次
- Efficient Reversal of Transductions of Sparse Graph ClassesJan Dreier, Jakub Gajarský, Michal PilipczukSTOC 2026 · 被引用 5 次
它引用的顶会 Paper3
- Twin-width I: tractable FO model checkingÉdouard Bonnet, Eun Jung Kim, Stéphan Thomassé, Rémi WatrigantFOCS 2020 · 被引用 82 次
- Twin-width II: small classesÉdouard Bonnet, Colin Geniet, Eun Jung Kim, Stéphan Thomassé 等SODA 2021 · 被引用 61 次
- Rankwidth meets stabilityJaroslav Nesetril, Patrice Ossona de Mendez, Michal Pilipczuk, Roman Rabinovich 等SODA 2021 · 被引用 23 次
相关 Paper
- 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 次
- 3D-grids are not transducible from planar graphsJakub Gajarský, Michal Pilipczuk, Filip PokrývkaLICS 2025 · 被引用 2 次
- Flip-Breakability: A Combinatorial Dichotomy for Monadically Dependent Graph ClassesJan Dreier, Nikolas Mählmann, Szymon TorunczykSTOC 2024 · 被引用 8 次
