{"id":"arxiv/2608.13964","url":"https://arxiv.org/abs/2608.13964","tags":["math.CO","cs.DM"],"score":0,"title":"A counterexample to the Albertson-Berman conjecture about induced forests in planar graphs","domain":"math.CO","source":"arxiv","authors":["Mikhail Makarov"],"reviews":0,"subject":"math.CO","summary":"For a graph $G$, denote by $a(G)$ the number of vertices in the largest induced forest in $G$. The Albertson-Berman conjecture, which had been open since 1979, states that $a(G) \\geq \\frac{n}{2}$ for every simple planar graph $G$ on $n$ vertices. Although the Albertson-Berman conjecture was recently resolved in the negative by constructing a counterexample with the help of AI, we independently found a counterexample to the Albertson-Berman conjecture without AI and present it in this article. Our counterexample is on $39$ vertices with $a(G)=19$. Finally, we indicate, without a full proof, a…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-08-14","reactions":{}}