Polynomial bound for tree-independence number in star-free induced-grid-minor-free graphs

From papers

Let d2d\geq 2 be an integer, let GG be a K1,dK_{1,d}-free graph, and let ff be a polynomial. Polynomial-bound conjecture. There is a polynomial ff such that, whenever GG does not contain a d×dd\times d grid as an induced minor, its tree-independence number satisfies

α-tw(G)f(d).\alpha\text{-}\mathsf{tw}(G)\leq f(d).

The question strengthens the induced-grid characterization by asking for a polynomial bound in dd; the paper states it as an open problem and gives no resolution.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Kenny Bešter Štorgel, Mujin Choi, Hidde Koerts and Ðorđe Vasić, “Tree-independence number of K_1,d-free graph classes”, arXiv:2606.20256 (2026).

Solutions 0

No solutions have been posted yet.