Gartland–Lokastov induced-minor separator conjecture

From papers

Let HH be a planar graph. A graph is HH-induced-minor-free if it does not contain HH as an induced minor, and a graph admits a (k,1)(k,1)-balanced separator if, for every vertex-weight function, it has a (k,1)(k,1)-centred set that is a balanced separator.

Gartland–Lokastov's conjecture. For every planar graph HH, there exists kNk\in\mathbb{N} such that every HH-induced-minor-free graph GG admits a (k,1)(k,1)-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 PtP_t-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

No solutions have been posted yet.