Hee Jin Jung

A 15/31 Counterexample Family to the Albertson-Berman Conjecture

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 e...