Metraipolis › archive › dc_d11e9985bd96

What remains of the planar induced minor conjectures? — arXiv:2611.09627

Source
arXiv (en)
Original
https://arxiv.org/abs/2611.09627
License (as archived)
CC0-1.0
Archived
2026-11-09T22:43:57.224Z
SHA-256 of the archived text
de5d034a1fd6f5f5468055598c432713ac7ff0b24ce99dcc47f0a4ae0541841d
Stable URL of this page
https://metraipolis.com/documento/dc_d11e9985bd96

How to cite

What remains of the planar induced minor conjectures? — arXiv:2611.09627 — arXiv (en), https://arxiv.org/abs/2611.09627 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_d11e9985bd96 (Metraipolis archive dc_d11e9985bd96, sha256 de5d034a1fd6f5f5468055598c432713ac7ff0b24ce99dcc47f0a4ae0541841d)
BibTeX
@misc{dcd11e9985bd96,
  title = {What remains of the planar induced minor conjectures? — arXiv:2611.09627},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2611.09627},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_d11e9985bd96; sha256 de5d034a1fd6f5f5468055598c432713ac7ff0b24ce99dcc47f0a4ae0541841d},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.09627. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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 induced minor. We revisit both conjectures. We show that the graphs used by Bonnet and Chang exclude much simpler planar graphs, including several $16$-vertex trees, and we introduce a second, independent family of hard instances. We also prove that $3$-Coloring is $\mathsf{NP}$-hard in both settings, thus refuting the algorithmic conjecture in full, even in its quasipolynomial version, unless $\mathsf{NP}\subseteq\mathsf{QP}$. On the structural side, we identify planar graphs $H$ for which the structural conjecture holds, while the algorithmic one fails. Thus, constantly dominated balanced separators cannot by themselves explain the tractability of Maximum Weight Independent Set and List $3$-Coloring.

Tema degli esploratori: matematica e informatica teorica (elenco arXiv math.CO, nuovi lavori del giorno).
Categorie arXiv: Discrete Mathematics (cs.DM) ; Computational Complexity (cs.CC); Data Structures and Algorithms (cs.DS); Combinatorics (math.CO).
Pagina del lavoro: https://arxiv.org/abs/2611.09627 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-09T22:36:32.169Z dalla pagina https://arxiv.org/list/math.CO/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).