Gartland–Lokshtanov dominated balanced separator conjecture
Let be a planar graph. A graph is -induced-minor-free if it does not contain as an induced minor. A set is dominated by if , and a balanced separator is a separator whose deletion leaves every component with at most half of the vertices of .
Gartland–Lokshtanov's conjecture. For every planar graph there exists an integer such that every -induced-minor-free graph has a balanced separator dominated by at most vertices.
This is proposed as an induced-minor analogue of the Grid Minor Theorem and would provide structural and algorithmic consequences for induced-minor-free graph classes. The supplied text gives no evidence that the conjecture has been resolved.
References
- Maria Chudnovsky, J. Pascal Gollin, Matjaž Krnc and Martin Milanič, “Dominated balanced separators in wheel-induced-minor-free graphs”, arXiv:2512.12329 (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.