The induced Grid Theorem for K1,dK_{1,d}-free graphs

Let k,dk,d be positive integers, and let GG be a graph. A graph is K1,dK_{1,d}-free if it has no induced subgraph isomorphic to K1,dK_{1,d}. The tree-independence number α\alpha-tw(G)\mathsf{tw}(G) is the minimum, over all tree-decompositions of GG, of the maximum independence number of a bag.

The induced Grid Theorem. There exists a function f:N2Nf:\mathbb{N}^2\rightarrow\mathbb{N} such that every K1,dK_{1,d}-free graph GG with α\alpha-tw(G)f(k,d)\mathsf{tw}(G)\geq f(k,d) contains the (k×k)(k\times k)-grid as an induced minor.

This is the conjectured induced analogue of the Grid Theorem for graphs of bounded induced degree. The paper discusses it as a target for the results developed here; its resolution remains open.

Sources & referencesView supporting material

Primary source

Mujin Choi and Sebastian Wiederrecht, “Excluding a Ladder as an Induced Minor in Graphs Without Induced Stars”, arXiv:2509.04026 (2025).

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.