Subpolynomial treewidth conjecture for induced-minor-free graphs

Let Wt×tW_{t\times t} be the tt-by-tt hexagonal grid and let Kt,tK_{t,t} be the complete bipartite graph with both sides of the bipartition of size tt. For a positive integer tt, let Ct\mathcal{C}_t be the class of graphs with no induced minor isomorphic to Kt,tK_{t,t} or Wt×tW_{t\times t}, and let Ct\mathcal{C}_t^* be the subclass consisting of graphs with no clique of size tt. Here tw(G)tw(G) denotes the treewidth of a graph GG. Subpolynomial treewidth conjecture. For every tNt\in{\mathbb N}, there is an integer d=d(t)d=d(t) such that every nn-vertex graph GCtG\in\mathcal{C}_t^* satisfies

tw(G)logdn.tw(G)\leq\log^d n.

The conjecture predicts a polylogarithmic treewidth bound for graphs excluding fixed induced minors and a fixed-size clique, which would support efficient or quasi-polynomial algorithms for problems such as Maximum Weight Independent Set on these classes. Its resolution is not supplied in the source context.

Sources & referencesView supporting material

Primary source

Maria Chudnovsky, Julien Codsi, David Fischer and Daniel Lokshtanov, “Induced minors and subpolynomial treewidth”, arXiv:2512.18835 (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.