Polylogarithmic tree-independence conjecture for induced-minor-free graphs

About 1 year old · traced to

For a positive integer tt, let Kt,tK_{t,t} be the complete bipartite graph, and let Wt×tW_{t\times t} be the t×tt\times t-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 tt, there is an integer d=d(t)d=d(t) such that for every n≥2n\ge2, every nn-vertex graph with no induced minor isomorphic to Kt,tK_{t,t} or to Wt×tW_{t\times t} has tree independence number at most log⁡dn\log^d n.

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

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.