Induced-minor-free product structure conjecture

About 1 year old · traced to

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 J⊠PJ\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 ⁣:N→Nf\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 J⊠PJ\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.

References

Primary source

Robert Hickingbotham, “Induced Minors, Asymptotic Dimension, and Baker's Technique”, arXiv:2508.06190 (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.