Subpolynomial treewidth conjecture for induced-minor-free graphs
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.
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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.