2025/01/13 by Gajarský, Jakub, Pilipczuk, Michał, Pokrývka, Filip · 1 citation
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Logic in Computer Science (cs.LO)
paper · doi:10.48550/arxiv.2501.07558
We prove that the class of 3D-grids is cannot be transduced from planar graphs, and more generally, from any class of graphs of bounded Euler genus. To prove our result, we introduce a new structural tool called slice decompositions, and show that every graph class transducible from a class of graphs of bounded Euler genus is a perturbation of a graph class that admits slice decompositions.