Gartland–Lokshtanov dominated balanced separator conjecture

From papers

Let HH be a planar graph. A graph GG is HH-induced-minor-free if it does not contain HH as an induced minor. A set SV(G)S\subseteq V(G) is dominated by CV(G)C\subseteq V(G) if SN[C]S\subseteq N[C], and a balanced separator is a separator whose deletion leaves every component with at most half of the vertices of GG.

Gartland–Lokshtanov's conjecture. For every planar graph HH there exists an integer kHk_H such that every HH-induced-minor-free graph GG has a balanced separator dominated by at most kHk_H 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

No solutions have been posted yet.