Mikołaj Bojańczyk

Mikołaj Bojańczyk, Pierre Ohlmann

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.