Gartland–Lokastov induced-minor separator conjecture
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.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Sources & referencesView supporting material
Primary source
Maria Chudnovsky and Robert Hickingbotham, “Coarse Balanced Separators and Tree-Decompositions”, arXiv:2505.06550 (2025).
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.