Logarithmic treewidth via four forbidden families

Conjecture 1.10 · arXiv:2109.01310

arXiv Conjecture high confidence— first stated 2022-09-07

Authors: Tara Abrishami, Maria Chudnovsky, Sepehr Hajebi, Sophie Spirkl

Status open medium confidence

Conjecture 1.10 from arXiv:2109.01310 posits logarithmic treewidth for graphs excluding K_t, K_{t,t}, subdivisions of W_{t\times t}, and line graphs of subdivisions of W_{t\times t} as induced subgraphs. No paper resolving this conjecture was found in five targeted web searches covering the period 2022–2026. The closely related work arXiv:2311.05066 (Alecu, Chudnovsky, Hajebi, Spirkl, 2023) characterises when H-free graph classes contain only basic treewidth obstructions, but does not prove the specific logarithmic bound of the conjecture. The conjecture remains open as of May 2026.

Reviewer notes. No follow-up resolving Conjecture 1.10 was found after 5 web calls. The conjecture is ~4.5 years old (arXiv ID 2109.01310, paper published 2022), so confidence is set to medium rather than high. The related paper arXiv:2311.05066 addresses basic obstructions in H-free graph classes but focuses on a structural characterisation (cleanness of the class) rather than the quantitative logarithmic treewidth bound that Conjecture 1.10 asserts.

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

Conjecture. For all $t \geq 0$ there exists $c = c(t)$ such that if $G$ is a graph with no $K_t$, no $K_{t,t}$, no subdivision of $W_{t \times t}$ and no line graph of a subdivision of $W_{t \times t}$ as induced subgraphs, then $\mathrm{tw}(G) \leq c \log(|V(G)|)$.

Context

The authors propose this as a natural extension of the main results and describe it as a variant of a conjecture of Sintiari and Trotignon [17]. It posits that excluding the four known families responsible for large treewidth (complete graphs, complete bipartite graphs, subdivided walls, line graphs of subdivided walls) as induced subgraphs forces treewidth to be at most logarithmic in the number of vertices.

Notes. PDF source — math appears clean.

Source paper

Induced subgraphs and tree decompositions III. Three-path-configurations and logarithmic treewidth
Tara Abrishami, Maria Chudnovsky, Sepehr Hajebi, Sophie Spirkl · 2022-09-07
https://arxiv.org/abs/2109.01310 PDF source