Graphs of unbounded linear cliquewidth must transduce all trees
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: if a class of graphs has unbounded linear cliquewidth, then it can produce all trees via some fixed MSO transduction.
Authors
- Pierre Ohlmann (ORCID: https://orcid.org/0000-0002-4685-5253)
- Mikołaj Bojańczyk (ORCID: https://orcid.org/0000-0002-7758-1072)
Institutions
- Centre National de la Recherche Scientifique (FR)
- Aix-Marseille Université (FR)
- University of Warsaw (PL)
Publication Details
- Published
- 2025-06-23
- DOI
- https://doi.org/10.1109/lics65433.2025.00058
- Primary Topic
- Interconnection Networks and Systems
- Type
- article
- Field-Weighted Citation Impact
- 0.00