Trotignon's bounded-treewidth conjecture for graphs excluding induced minors

For a graph GG, a string representation is an assignment of its vertices to curves in the plane such that two curves intersect if and only if the corresponding vertices are adjacent. An outerstring representation is a string representation in which all curves lie in the upper half-plane and each curve has exactly one endpoint on the xx-axis; graphs admitting such a representation are outerstring graphs. Let Wt×tW_{t \times t} denote the t×tt \times t wall and let Kt,tK_{t,t} denote the complete bipartite graph with parts of size tt.

Trotignon's conjecture. For all r,tNr,t\in\mathbb{N}, there exists c=c(r,t)Nc=c(r,t)\in\mathbb{N} such that for every graph GG, if GG does not contain Wt×tW_{t \times t} or Kt,tK_{t,t} as an induced minor, and every induced subgraph HH of GG that is an outerstring graph satisfies

tw(H)r,\operatorname{tw}(H)\leq r,

then

tw(G)c.\operatorname{tw}(G)\leq c.

The conjecture would give a uniform bound on the treewidth of graphs excluding these induced minors when all their outerstring induced subgraphs have bounded treewidth. It is refuted by the construction cited in the source.

Sources & referencesView supporting material

Primary source

Maria Chudnovsky, David Fischer, Sepehr Hajebi, Sophie Spirkl and Bartosz Walczak, “A simple layered-wheel-like construction”, arXiv:2507.06169 (2026).

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.