Gartland and Lokshtanov's induced grid minor conjecture
Gartland and Lokshtanov's induced grid minor conjecture
Given a graph , a set is a balanced separator if every component of satisfies . For sets , say that dominates if .
Induced Grid Minor Conjecture. There exists a function such that for every planar graph , every -induced-minor-free graph has a balanced separator dominated by 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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.