Polylogarithmic tree-independence conjecture for induced-minor-free graphs
For a positive integer , let be the complete bipartite graph, and let be the -wall. An induced minor is a graph obtained by taking an induced subgraph and contracting pairwise vertex-disjoint connected subgraphs. The tree independence number is the minimum, over all tree decompositions, of the maximum independence number of a bag.
Polylogarithmic tree-independence conjecture. For every positive integer , there is an integer such that for every , every -vertex graph with no induced minor isomorphic to or to has tree independence number at most .
This is presented as a further goal toward understanding induced-minor obstructions to polylogarithmic tree independence. The source describes the preceding conjecture and the methods developed there as promising steps, but gives no resolution.
References
Primary source
Maria Chudnovsky, Julien Codsi, Daniel Lokshtanov, Martin Milanič and Varun Sivashankar, “Tree independence number V. Walls and claws”, arXiv:2501.14658 (2025).
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.