11 problems

Let $\mathscr C$ be a class of TOWS graphs, and let $\mathsf{Sp}(\mathscr C)$ be the class obtained by the paper's sparsifying transduction. Let $\Pi_S$ be a downset of weakly spar…

Let $\mathcal C$ be a graph class. Following the paper, say that $\mathcal C$ is in the dense analogue of bounded expansion if, for every weakly sparse graph class $\mathcal D$ suc…

Transduction preservation conjecture. The property of being a perturbation of a class of bounded expression-stable $\ca P^\circ$-clique-width is preserved under taking first-order…

Expression-stability conjecture. There is a function $g:\mathbb{N}\to\mathbb{N}$ such that each $(\ca Q_r^\circ,\ell)$-expression constructed in the proof of the transduction lemma…

Linear cliquewidth CMSO obstruction conjecture. A class of graphs $\mathscr{C}$ has bounded linear cliquewidth if and only if the class of trees cannot be $\mathsf{CMSO}$-transduce…

Surface transduction-order conjecture. Let $\Sigma$ and $\Gamma$ be surfaces such that $\Sigma\not\preccurlyeq\Gamma$. Then

Gajarsky–Pilipczuk–Toruńczyk's cliquewidth obstruction conjecture. A class of graphs $\mathscr{C}$ has unbounded cliquewidth if and only if $\mathscr{C}$ transduces a class…

Monadic stability characterization conjecture. A class of graphs is monadically stable if and only if it is a first-order transduction of a nowhere dense class of graphs.

For each positive integer $n$, let $_n$ be the class of graphs of pathwidth at most $n$, and let $_n$ be the class of graphs of treewidth at most $n$. Two graph classes are non-com…

Let … the class of all paths, … the class of all graphs. For graph classes … , write $\trianglelefteq_{}$ when there is an MSO transduction from … , and write $\triangleleft_{}$ wh…

Let $\cf G$ be a class of graphs, let ${\mathrm{CMSO}_1}\xspace$ denote counting monadic second-order logic with one free set-variable type, let $\tau$ be a…