Gartland and Lokshtanov's induced grid minor conjecture

Given a graph GG, a set SV(G)S\subseteq V(G) is a balanced separator if every component CC of GSG-S satisfies V(C)V(G)/2|V(C)|\le |V(G)|/2. For sets X,YV(G)X,Y\subseteq V(G), say that XX dominates YY if YN[X]Y\subseteq N[X].

Induced Grid Minor Conjecture. There exists a function ff such that for every planar graph HH, every HH-induced-minor-free graph GG has a balanced separator dominated by f(H)f(H) vertices.

The source notes that the conjecture was originally stated for grid graphs and is equivalent to the planar-graph formulation because every planar graph is an induced minor of a sufficiently large grid. Its status is open.

Sources & referencesView supporting material

Primary source

Claire Hilaire, Martin Milanič and Đorđe Vasić, “Treewidth versus clique number. V. Further connections with tree-independence number”, arXiv:2505.12866 (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.