Polynomial utw bound for minor-free classes

Question 1 · 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 1 from arXiv:2307.02816 asks whether the upper bound on the underlying treewidth of X-minor-free graph classes given by the paper's main theorem can be improved to a polynomial dependence on td(X). No follow-up paper resolving or substantially improving this bound was found in the indexed literature. The source paper itself was published in Combinatorica (2025), and the polynomial-bound question remains open as of the review date.

Reviewer notes. The source paper appeared in Combinatorica 2025 (DOI 10.1007/s00493-025-00168-w) but the journal page was behind a paywall and could not be verified for any updated open-question discussion. No paper directly addressing Question 1 — whether utw(G_X) is polynomial in td(X) — was found across three targeted web searches. The conjecture is recent (2023) and the absence of follow-up evidence supports open status with high confidence.

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

Question. Can the upper bound on $\operatorname{utw}(\mathcal{G}_{X})$ in Equation 1 be improved? In particular, is $\operatorname{utw}(\mathcal{G}_{X})$ at most a polynomial function of $\operatorname{td}(X)$?

Context

The paper's main theorem (Theorem 1) gives an upper bound on the underlying treewidth of $X$-minor-free graph classes in terms of $\operatorname{td}(X)$. This question opens the concluding open-problems section and asks whether that bound can be tightened to a polynomial dependence on $\operatorname{td}(X)$.

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