Induced-minor-free product structure conjecture

From papers

Let HH be a graph. For a graph GG, being HH-induced-minor-free means that GG does not contain HH as an induced minor. Let JPJ\boxtimes P denote the strong product of graphs JJ and PP, and let tw(J)\operatorname{tw}(J) denote the treewidth of JJ.

Induced-minor-free product structure conjecture. There is a function f ⁣:NNf\colon \mathbb{N}\to\mathbb{N} such that every HH-induced-minor-free graph GG with maximum degree at most Δ\Delta is isomorphic to a subgraph of JPJ\boxtimes P for some graph JJ with tw(J)f(Δ)\operatorname{tw}(J)\leqslant f(\Delta) and for some path PP.

This is proposed as a common strengthening of product-structure results for planar and bounded-degree minor-free graphs. Its resolution is not given in the source.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Robert Hickingbotham, “Induced Minors, Asymptotic Dimension, and Baker's Technique”, arXiv:2508.06190 (2025).

Solutions 0

No solutions have been posted yet.