Topological-minor exclusion product structure

Question 2 · arXiv:2307.02816

arXiv Question high confidence— first stated 2023-07-06

Authors: Vida Dujmović, Robert Hickingbotham, Jędrzej Hodor, Gweanël Joret, Hoang La, Piotr Micek, Pat Morin, Clément Rambaud, David R. Wood

Status open high confidence

Question 2 asks whether the main result of arXiv:2307.02816 (which holds in the excluded-minor setting) extends to the excluded-topological-minor setting, with the treewidth of H bounded by f(td(X)) rather than |V(X)|. Campbell et al. (arXiv:2206.02395) proved the weaker version with tw(H) ≤ |V(X)|, and that bound is tight for complete graphs. Subsequent product-structure work (arXiv:2410.20333, Liu–Norin–Wood 2024) addresses odd-minor-free graphs but not the topological-minor setting. No paper resolving Question 2 was found in the indexed literature as of May 2026.

Reviewer notes. Campbell et al. (arXiv:2206.02395, published in Combinatorics Probability and Computing 2023) proved the topological-minor analogue with tw(H) ≤ |V(X)|; this bound is tight for complete graphs. The source paper's Theorem 2 achieves tw(H) ≤ f(td(X)) in the excluded-minor setting (not topological minor). The gap between |V(X)| and f(td(X)) in the topological-minor setting is the open question. No follow-up resolving this was found; arXiv:2410.20333 (Liu–Norin–Wood 2024) works in the minor and odd-minor settings only.

Auto-reviewed 2026-05-15 with claude-sonnet-4-6 (web search enabled).

Question. Is there a function $f$ such that for every graph $X$ there exists a function $c$ such that for every positive integer $t$ and for every graph $G$ with $\operatorname{tw}(G)<t$ that does not contain $X$ as a topological minor, there exists a graph $H$ of treewidth at most $f(\operatorname{td}(X))$ such that $G\mathrel{\ooalign{\raise 0.75348pt\hbox{$\subset$}\cr\raise-3.87495pt\hbox{\scalebox{0.9}{$\sim$}}\cr}}H\boxtimes K_{c(t)}$?

Context

This question asks whether Theorem 2 can be extended from the excluded-minor setting to the excluded-topological-minor setting. Campbell et al. proved a weaker version with $\operatorname{tw}(H)\leqslant|V(X)|$, and that bound is tight for complete graphs.

Notes. The subgraph-isomorphism symbol uses \ooalign and is reproduced verbatim from the LaTeX source.

Source paper

The grid-minor theorem revisited
Vida Dujmović, Robert Hickingbotham, Jędrzej Hodor, Gweanël Joret, Hoang La, Piotr Micek, Pat Morin, Clément Rambaud, David R. Wood · 2023-07-06
https://arxiv.org/abs/2307.02816