Gartland–Lokshtanov dominated balanced separator conjecture
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.
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, J. Pascal Gollin, Matjaž Krnc and Martin Milanič, “Dominated balanced separators in wheel-induced-minor-free graphs”, arXiv:2512.12329 (2025).
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.