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

Less than 1 year old · traced to

Let d≥2d\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.

References

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).

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.