{"id":"arxiv/2608.17350","url":"https://arxiv.org/abs/2608.17350","tags":["math.CO"],"score":0,"title":"A 15/31 Counterexample Family to the Albertson-Berman Conjecture","domain":"math.CO","source":"arxiv","authors":["Heejae Jung"],"reviews":0,"subject":"math.CO","summary":"For a graph $G$, let $a(G)$ be the maximum number of vertices in an induced forest. The Albertson-Berman conjecture, posed in 1979, asserts that every $n$-vertex planar graph satisfies $a(G)\\ge n/2$. Borodin's bound $a(G)\\ge 2n/5$ remains the general lower bound toward this problem. We disprove the conjecture with an explicit 31-vertex plane triangulation $T$ satisfying $a(T)=15$. Moreover, for every integer $k\\ge2$, we construct a simple planar graph $M_k$ with $|V(M_k)|=31k$ and $a(M_k)=15k$, so that $a(M_k)/|V(M_k)|=15/31<1/2$. Every member of the family has minimum degree five. The…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-08-18","reactions":{}}