Albertson–Berman induced-forest conjecture

The Albertson–Berman conjecture, posed in 1979, asserts that every planar graph contains an induced forest on at least half its vertices. August 2026 work claims this statement is false.

Known results

• Borodin’s acyclic $5$-colorability gives $a(G)\geq \frac{2}{5}n$ for planar graphs.
• The conjecture holds for planar graphs of girth at least $5$.
• The conjecture would imply an independent set of size at least $\frac{n}{4}$ without using the Four Color Theorem.

August 2026 claimed disproofs and refinement

One preprint constructs a $31$-vertex plane triangulation with $a(G)=15$, and an infinite family with ratio $\frac{15}{31}<\frac{1}{2}$. Another claims a $39$-vertex example with ratio $\frac{19}{39}$. A newer report claims to determine the minimum counterexample order, increase connectivity, and improve the ratio further; these claims remain unverified, and one reported construction is explicitly incomplete.

Current status (as of August 2026): the conjecture has claimed counterexamples, including a reported ratio of $\frac{15}{31}$, but no independent verification is recorded and the exact post-disproof structural conclusions remain unconfirmed.