Albertson–Berman conjecture on induced forests in planar graphs

The conjecture, open since 1979, asserts that every simple planar graph on $n$ vertices contains an induced forest with at least $n/2$ vertices. Two 2026 sources now claim explicit counterexamples, so the assertion is no longer plausibly an untouched open problem, but neither claim has independent confirmation.

Known results

• Borodin’s acyclic $5$-colorability theorem gives $a(G)\geq 2n/5$.
• Disjoint copies of $K_4$ show that the conjectured $n/2$ bound would be tight.
• A 2016 paper records the statement as a challenging conjecture and the $2n/5$ bound as the best general lower bound.

August 2026 claimed counterexamples

An arXiv preprint claims a fully proved simple planar graph $G_{39}$ with $a(G_{39})=19$, giving $19/39<1/2$, while calling the manuscript unfinished and unpolished. A separate Zenodo record claims $3$-connected maximal planar graphs $M_k$ with $31k$ vertices and $a(M_k)=15k$, and supplies a Python verifier; neither claim has independent verification or a reported retraction.

Current status (as of August 2026): The $n/2$ conjecture remains unverified and is now contradicted by two claimed explicit constructions; independent checking is needed, and the best valid lower bound and optimal constant remain open.