First-order transducibility among classes of sparse graphs

Jakub Gajarský, Jeremi Gładkowski, Jan Jedelský +2

We prove several negative results about first-order transducibility for classes of sparse graphs: - for every $t\in \mathbb{N}$, the class of graphs of treewidth at most $t+1$ is…