Gartland and Lokshtanov's induced grid minor conjecture

About 1 year old · traced to

Given a graph GG, a set S⊆V(G)S\subseteq V(G) is a balanced separator if every component CC of G−SG-S satisfies ∣V(C)∣≤∣V(G)∣/2|V(C)|\le |V(G)|/2. For sets X,Y⊆V(G)X,Y\subseteq V(G), say that XX dominates YY if Y⊆N[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.

References

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.