For every pair of integers t≥ 2 and s≥ 1, there exists a constant c=c(t,s) such that every graph G with no induced subgraph isomorphic to K_t,t and satisfying simw(G)≤ s also satisfies tree-alpha(G)≤ c. Equivalently, for each fixed t, bounded sim-width in the class of induced K_t,t-free graphs implies bounded tree-independence number.

Bounded sim-width and tree-independence conjecture

For every pair of integers $t\ge 2$ and $s\ge 1$ , there exists a constant $c=c(t,s)$ such that every graph $G$ with no induced subgraph isomorphic to $K_{t,t}$ and satisfying $simw(G)\le s$ also satisfies $tree\text{-}\alpha(G)\le c$ . Equivalently, for each fixed $t$ , bounded sim-width in the class of induced $K_{t,t}$ -free graphs implies bounded tree-independence number.

References

Primary source

arXiv

Additional references

Sim-Width, Induced Matching Treewidth, and Tree-Independence Number in Induced K_{t,t}-Free Graphs — arXiv — Mengyuan Niu, Xiumei Wang

graph-theory structural-graph-theory

Posted 2 weeks ago · edited 2 weeks ago

Progress summary

Refreshed 2 weeks ago

Claimed solved

A September 2026 preprint claims to settle the conjecture and substantially improves the quantitative bound, but the result has not been independently verified.

The conjecture asks whether excluding a fixed induced biclique from a graph class of bounded sim-width forces bounded tree-independence number. Earlier literature recorded this as unresolved, including the related question for induced matching treewidth.

September 2026 preprint

Mengyuan Niu and Xiumei Wang claim the implication for induced $K_{t,t}$ -free graphs, answering questions of Abrishami et al., Brettell et al., and Alon et al. They report the bound $O_t((s+1)^{2t^2-2t})$ , improving the earlier exponent $3t^2+1$ , together with a polynomial-in- $t$ bound when induced matching treewidth is fixed. This is an unrefereed arXiv claim, not an independently verified resolution.

Current status (as of September 2026): The conjecture is claimed solved by Niu and Wang's September 2026 preprint, with improved bounds, but the proof remains unverified; prior published sources treated the implication as open.

Sources

No solutions have been posted yet.