Gartland–Lokastov induced-minor separator conjecture

About 1 year old · traced to

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 k∈Nk\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.

References

Primary source

Maria Chudnovsky and Robert Hickingbotham, “Coarse Balanced Separators and Tree-Decompositions”, arXiv:2505.06550 (2025).

Progress summary

Never refreshed

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.