Congested shallow-minor obstruction for toroidal graphs
Congested shallow-minor obstruction for toroidal graphs
A graph is a congestion- depth- minor of a graph if it has a congestion- depth- minor model in : each vertex of is represented by a connected subgraph of of radius at most , adjacent vertices of have intersecting or adjacent branch sets, and every vertex of belongs to at most branch sets.
Toroidal shallow-minor conjecture. There is no constant with the following property: every toroidal graph is a congestion- depth- minor of a planar graph.
This is proposed as a combinatorial stepping stone toward the surface transduction-order conjecture. The survey presents it as an open question.
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.