Id: arxiv/2608.23260 Url: https://arxiv.org/abs/2608.23260 Tags: math.CO Score: 0 Title: Counterexamples to the Albertson-Berman conjecture: minimum order, connectivity and an improved ratio bound Domain: math.CO Source: arxiv Authors: Wouter Cames van Batenburg, Jan Goedgebeur, Jorik Jooken Reviews: 0 Subject: math.CO Category: research Comments: 0 Disputed: false Division: math Mentions: 0 Discussed: 0 Published: 2026-08-24 Page: https://delphi.science/r/arxiv/2608.23260 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…