Tree-independence number via induced biclique number
Question 5.3 · arXiv:2511.03864
Status open high confidence
The source paper (arXiv:2511.03864) itself establishes the main partial result: for any K_{t,t}-free graph class, tree-independence number and induced matching treewidth are polynomially related via the Kövári–Sós–Turán theorem, improving the exponential bound of Abrishami et al. (arXiv:2405.04617). Question 5.3 asks whether this polynomial relationship holds in full generality—bounding tree-independence number by a polynomial in both induced matching treewidth and the induced biclique number—without assuming K_{t,t}-freeness a priori. No follow-up paper resolving this question was found in the literature as of May 2026.
Reviewer notes. No follow-up resolving Question 5.3 was found. The conjecture is equivalent to Question 5.2 (as stated in the paper) and was posted in November 2025; absence of resolution after a wide search gives high confidence it remains open. A related 2026 paper (arXiv:2604.01999) studies tree-independence number for graphs excluding a 6-vertex path and a (2,t)-biclique, but addresses a different conjecture. The paper arXiv:2405.04617 (Abrishami et al., SIAM JDM 2025) proved the qualitative boundedness result with an exponential bound, predating the source paper.
Context
The induced biclique number of $G$ is the largest nonnegative integer $t$ such that $G$ contains an induced subgraph isomorphic to $K_{t,t}$. This question is an equivalent restatement of Question 5.2 using the induced biclique number, and is noted as closely related to recent work bounding tree-independence number in terms of clique-like parameters.
Notes. Explicitly stated by the authors to be equivalent to Question 5.2.
Source paper
Induced matching treewidth and tree-independence number, revisited
Noga Alon, Martin Milanič, Paweł Rzążewski · 2025-11-05
https://arxiv.org/abs/2511.03864