Congested shallow-minor obstruction for toroidal graphs

A graph HH is a congestion-cc depth-dd minor of a graph GG if it has a congestion-cc depth-dd minor model in GG: each vertex of HH is represented by a connected subgraph of GG of radius at most dd, adjacent vertices of HH have intersecting or adjacent branch sets, and every vertex of GG belongs to at most cc branch sets.

Toroidal shallow-minor conjecture. There is no constant kNk\in\mathbb N with the following property: every toroidal graph is a congestion-kk depth-kk 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

Never refreshed

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.