Transduction order of graph classes embeddable in surfaces
Transduction order of graph classes embeddable in surfaces
A surface is a compact -dimensional manifold without boundary. Write if every graph embeddable in is also embeddable in , and let be the class of graphs embeddable in . Write when is first-order transducible from .
Surface transduction-order conjecture. Let and be surfaces such that . Then
This conjecture asserts that, among graph classes embeddable in fixed surfaces, the obvious inclusions are the only transducibility relations. It is not known even for the torus and the sphere, where it asks whether toroidal graphs are first-order transducible from planar graphs.
Sources & referencesView supporting material
Primary source
Michał Pilipczuk, “Graph classes through the lens of logic”, arXiv:2501.04166 (2025).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.