Trees in graphs of large linear cliquewidth
This work addresses a foundational gap in graph theory by generalizing a key theorem to dense graphs, with implications for the total order of cmso transductions, though it is incremental as it builds on existing concepts like cliquewidth and linear cliquewidth.
The paper tackles the problem of extending the Pathwidth Theorem to dense graphs by proving that any graph class with bounded cliquewidth and unbounded linear cliquewidth contains arbitrarily large tree-like patterns as induced subgraphs, which mso transduce all trees and fo transduce subdivisions of all binary trees. This result completes the proof that the cmso transduction order is total over classes of finite graphs.
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.