Subpolynomial treewidth conjecture for induced-minor-free graphs

About 1 year old · traced to

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 t∈Nt\in{\mathbb N}, there is an integer d=d(t)d=d(t) such that every nn-vertex graph G∈Ct∗G\in\mathcal{C}_t^* satisfies

tw(G)≤log⁡dn.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.

References

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.