Metraipolis › archive › dc_ab77721826fa

Counterexamples to the Albertson-Berman conjecture: minimum order, connectivity and an improved ratio bound — arXiv:2608.23260

Source
arXiv (en)
Original
https://arxiv.org/abs/2608.23260
License (as archived)
CC0-1.0
Archived
2026-10-18T08:33:23.610Z
SHA-256 of the archived text
6aa5e8c4a3efb2f840cde7a2f5cc5775464cc742643ae51ebb5294029bb1ebd4
Stable URL of this page
https://metraipolis.com/documento/dc_ab77721826fa

How to cite

Counterexamples to the Albertson-Berman conjecture: minimum order, connectivity and an improved ratio bound — arXiv:2608.23260 — arXiv (en), https://arxiv.org/abs/2608.23260 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_ab77721826fa (Metraipolis archive dc_ab77721826fa, sha256 6aa5e8c4a3efb2f840cde7a2f5cc5775464cc742643ae51ebb5294029bb1ebd4)
BibTeX
@misc{dcab77721826fa,
  title = {Counterexamples to the Albertson-Berman conjecture: minimum order, connectivity and an improved ratio bound — arXiv:2608.23260},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2608.23260},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_ab77721826fa; sha256 6aa5e8c4a3efb2f840cde7a2f5cc5775464cc742643ae51ebb5294029bb1ebd4},
  year = {2026}
}

Archived text

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

In 1979, Albertson and Berman conjectured that every planar graph $G$ contains an induced forest of order at least $|V(G)|/2$. This long-standing conjecture was recently disproved by several explicit counterexamples, which naturally led to several extremal and structural questions that we answer. We combine mathematical arguments and exhaustive computations to show that the minimum order of a counterexample is $29$. We also construct infinitely many $4$-connected $5$-edge-connected counterexamples (and show that the unique such counterexample of minimum order has order $41$), whereas previously all known counterexamples had vertex-connectivity at most $3$. Furthermore, we construct an infinite family of planar graphs on $n$ vertices whose maximum induced forests have order at most $\frac{25}{52}n$, thereby improving the previous best upper bound. This family also yields infinitely many counterexamples (for every integer $d \geq 7$) to a conjecture of Chappell and Pelsmajer concerning induced forests of maximum degree at most $d$.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-08-25 in math.CO).
Categorie arXiv: Combinatorics (math.CO).
Pagina del lavoro: https://arxiv.org/abs/2608.23260 — 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-10-18T08:27:54.454Z dalla pagina https://arxiv.org/catchup/math.CO/2026-08-25?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).