Polylogarithmic Treewidth in Induced-Subgraph-Free Graph Classes

Definitions and mathematical statement

For a finite graph $G$, a tree decomposition consists of a finite tree $T$ and bags $B_x\subseteq V(G)$, indexed by $x\in V(T)$, such that every vertex belongs to a bag, the endpoints of every edge belong together to a bag, and, for each vertex $v$, the nodes $x$ with $v\in B_x$ induce a connected subtree of $T$. Its width is $\max_{x\in V(T)}|B_x|-1$, and the treewidth $\operatorname{tw}(G)$ is the minimum width of a tree decomposition of $G$.

The supplied record describes $\mathcal C_t^*$ as a hereditary graph class, meaning a class closed under taking induced subgraphs. Its literature assessment further describes the relevant classes as induced-minor-free. However, the record gives neither a definition of $\mathcal C_t^*$ nor its forbidden configurations. These descriptions do not determine the class. The precise graph conventions and the base of the logarithm are also not supplied.

Subject to recovering these missing definitions and conventions, the question labeled Conjecture 3 in the supplied excerpt is the following statement schema: \[ \forall t\in{\mathbb{Z}}_{\geq 1}\;\exists d=d(t)\in{\mathbb{Z}}\;\forall n\in{\mathbb{Z}}_{\geq 3}\;\forall G\in\mathcal C_t^*,\qquad |V(G)|=n\ \Longrightarrow\ \operatorname{tw}(G)\leq (\log n)^{d(t)}. \] Here $d(t)$ depends only on $t$, and the bound has no additional multiplicative constant. The restriction $n>2$ is explicit in the original excerpt and is retained, although omitted from the cleaned statement. The record specifies an integer exponent, without explicitly requiring it to be positive. Without the definition of $\mathcal C_t^*$, this schema is not a self-contained conjecture.

The supplied surrounding passage reports a weaker result, labeled Theorem 4 and attributed to reference [1], with parameters $\epsilon(t)\in(0,1]$ and $c(t)\in{\mathbb{N}}$, and describes its treewidth bound as subpolynomial. The displayed bound has corrupted exponent placement in the supplied transcription, so no exact formula is asserted here.

The subsequent context introduces, for a vertex set $S\subseteq V(G)$ and a positive integer $r$, the quantity \[ \alpha_r(S)=\max\left\{|I|:I\subseteq S,\ \operatorname{dist}_G(u,v)>r\text{ for every two distinct }u,v\in I\right\}. \] It then mentions analogous parameters for tree decompositions and graphs, states that tree-$\alpha_1$ was introduced in reference [5] for studying classes containing complete graphs of unbounded size, and begins discussing another conjecture involving $\omega(G)$, the largest size of a complete subgraph of $G$. That further conjecture is not supplied and is not part of the target statement above.

Short English statement

The question asks whether, for every positive integer $t$, one integer exponent depending only on $t$ bounds the treewidth of every $n$-vertex graph in $\mathcal C_t^*$ by $(\log n)^{d(t)}$, for $n>2$. The supplied record labels this question open, but omits the definition of $\mathcal C_t^*$; the draft therefore requires source clarification and human mathematical review.

Sources

• Local UnsolvedMath registry: supplied record with permanent ID $30006545$, exact source problem code catalogue entry, in the Oberwolfach Reports Open Problems collection. No individual proposer is identified; the supplied proposed year is 2026.
• Supplied report citation: Combinatorics (2026), Oberwolfach Reports, DOI 10.4171/owr/2026/1, pp. 5--79. https://doi.org/10.4171/owr/2026/1. The extracted target is labeled Conjecture 3. This reference is supplied provenance and has not been independently consulted for this draft.
• Supplied literature source: Chudnovsky et al., Induced minors and subpolynomial treewidth. https://arxiv.org/abs/2512.18835. The record associates this work with the weaker subpolynomial bound; its claims and its correspondence with the excerpt's reference [1] have not been independently verified.
• Literature assessment dated exactly 2026-08-22: the supplied curation labels the conjectured polylogarithmic bound open and reports a weaker subpolynomial bound for the same induced-minor-free classes. This is supplied dated curation, not an independently verified literature assessment; the source itself requests independent verification of time-sensitive status and cited claims.
• The registry assigns the statement status corrected_verified and reports that the official report was checked, the question isolated, and its notation repaired. These are supplied source-verification claims, not verification performed for this draft. Bibliographic details for the excerpt's numbered references [1] and [5] are not supplied.