Gartland–Lokastov induced-minor separator conjecture
Let be a planar graph. A graph is -induced-minor-free if it does not contain as an induced minor, and a graph admits a -balanced separator if, for every vertex-weight function, it has a -centred set that is a balanced separator.
Gartland–Lokastov's conjecture. For every planar graph , there exists such that every -induced-minor-free graph admits a -balanced separator.
This conjecture proposes that excluding a large grid as an induced minor is the only obstruction to balanced separators in hereditary graph classes. It is known for several classes, including -free, even-hole-free, and three-path-configuration-free graphs, but remains open in general.
References
Primary source
Maria Chudnovsky and Robert Hickingbotham, “Coarse Balanced Separators and Tree-Decompositions”, arXiv:2505.06550 (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
No solutions have been posted yet.