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.
References
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
No solutions have been posted yet.