Stable graphs of bounded twin-width
| Autor: | Jakub Gajarský, Michał Pilipczuk, Szymon Toruńczyk |
|---|---|
| Rok vydání: | 2022 |
| Předmět: | |
| Zdroj: | Proceedings of the 37th Annual ACM/IEEE Symposium on Logic in Computer Science 37th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2022 |
| DOI: | 10.1145/3531130.3533356 |
| Popis: | We prove that every class of graphs $\mathscr C$ 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 $\chi$-bounded. Comment: 45 pages, 5 figures |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|