Polynomial tree-α bound in K_{t,t}-free graphs

Question 5.2 · arXiv:2511.03864

arXiv Question high confidence— first stated 2025-11-05

Authors: Noga Alon, Martin Milanič, Paweł Rzążewski

Status open high confidence

Question 5.2 is left open in the source paper arXiv:2511.03864. The paper's main result (Theorem 1.2) establishes tree-α(G) = O_t(μ^{3t²+1}) for K_{t,t}-free graphs with tree-μ(G) ≤ μ, giving a polynomial bound in μ for fixed t; however, Question 5.2 asks for the reverse direction: a polynomial bound in t for fixed μ. Lemma 5.1 of the paper shows the existing bound involves N(s,s,2) which is exponential in s, motivating the question, but does not rule out a polynomial in t for fixed μ. No follow-up paper resolving this question was found in the indexed literature in the six months since posting.

Reviewer notes. The paper was posted November 2025 and Question 5.2 is explicitly left open. The main theorem gives tree-α(G) = O_t(μ^{3t²+1}), a polynomial in μ (for fixed t) but with t-dependent exponent, so it does not answer Question 5.2. No follow-up resolving this specific question was found after 5 web calls; the conjecture is open with high confidence given its recency.

Auto-reviewed 2026-05-14 with claude-sonnet-4-6 (web search enabled).

Question. Is is true that for every positive integer $\mu$ there exists a polynomial $\mathsf{p}_{\mu}$ such that every $K_{t,t}$-free graph $G$ with $\operatorname{tree\textnormal{-}\mu}(G)\leqslant\mu$ satisfies $\operatorname{tree\textnormal{-}\alpha}(G)\leqslant\mathsf{p}_{\mu}(t)$?

Context

Lemma 5.1 shows that the smallest integer $\mathsf{N}(s,s,2)$ appearing in the bound from Abrishami et al. is not bounded by any polynomial in both parameters, motivating the question of whether a polynomial bound in $t$ alone (for fixed $\mu$) is achievable. The question asks specifically whether tree-independence number can be bounded polynomially in the induced biclique exclusion parameter $t$ for graphs of bounded induced matching treewidth.

Also stated in

Induced matching treewidth and tree-independence number, revisited (2025-11-05)

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