Trees in graphs of large linear cliquewidth
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910110720196608 |
|---|---|
| author | Bojańczyk, Mikołaj Ohlmann, Pierre |
| author_facet | Bojańczyk, Mikołaj Ohlmann, Pierre |
| contents | The Pathwidth Theorem states that if a class of graphs has unbounded pathwidth, then it contains all trees as graph minors. We prove a similar result for dense graphs. More precisely, we give a finite family of tree-like patterns and prove that every graph class of bounded cliquewidth and unbounded linear cliquewidth contains arbitrarily large patterns as induced subgraphs. These patterns mso transduce all trees, and fo transduce subdivisions of all binary trees. In particular, our result provides the missing piece in establishing that the cmso transduction order is total over classes of finite graphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_17556 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Trees in graphs of large linear cliquewidth Bojańczyk, Mikołaj Ohlmann, Pierre Logic in Computer Science The Pathwidth Theorem states that if a class of graphs has unbounded pathwidth, then it contains all trees as graph minors. We prove a similar result for dense graphs. More precisely, we give a finite family of tree-like patterns and prove that every graph class of bounded cliquewidth and unbounded linear cliquewidth contains arbitrarily large patterns as induced subgraphs. These patterns mso transduce all trees, and fo transduce subdivisions of all binary trees. In particular, our result provides the missing piece in establishing that the cmso transduction order is total over classes of finite graphs. |
| title | Trees in graphs of large linear cliquewidth |
| topic | Logic in Computer Science |
| url | https://arxiv.org/abs/2501.17556 |