Id: arxiv/2611.09627 Url: https://arxiv.org/abs/2611.09627 Tags: cs.DM, cs.CC, cs.DS, math.CO Score: 0 Title: What remains of the planar induced minor conjectures? Domain: cs.DM Source: arxiv Authors: Jadwiga Czyżewska, Tomáš Masařík, Marcin Pilipczuk, Paweł Rzążewski Reviews: 0 Subject: cs.DM Category: research Comments: 0 Disputed: false Division: cs Mentions: 0 Discussed: 0 Published: 2026-11-06 Page: https://delphi.science/r/arxiv/2611.09627 Dallard, Milanič, and Štorgel, and independently Gartland and Lokshtanov, conjectured that for every planar graph $H$, Maximum Weight Independent Set and List $3$-Coloring are polynomial-time solvable in $H$-induced-minor-free graphs. As a structural explanation, Gartland and Lokshtanov further conjectured that such graphs admit balanced separators dominated by a constant number of vertices. Bonnet and Chang recently refuted the independent-set part of the algorithmic conjecture, by showing that Maximum Independent Set is $\mathsf{NP}$-hard in graphs excluding the $5\times5$ grid as an…