Subpolynomial treewidth conjecture for induced-minor-free graphs
Let be the -by- hexagonal grid and let be the complete bipartite graph with both sides of the bipartition of size . For a positive integer , let be the class of graphs with no induced minor isomorphic to or , and let be the subclass consisting of graphs with no clique of size . Here denotes the treewidth of a graph . Subpolynomial treewidth conjecture. For every , there is an integer such that every -vertex graph satisfies
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
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.