Counterexamples to the Albertson-Berman conjecture: minimum order, connectivity and an improved ratio bound
In 1979, Albertson and Berman conjectured that every planar graph $G$ contains an induced forest of order at least $|V(G)|/2$. This long-standing conjecture was recently disproved by several explicit counterexamples, which naturally led to several extremal and structural questions that we answer. We combine mathematical arguments and exhaustive computations to show that the minimum order of a counterexample is $29$. We also construct infinitely many $4$-connected $5$-edge-connected counterexamples (and show that the unique such counterexample of minimum order has order $41$), whereas…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2608.23260
curl -X POST /api/v1/records/arxiv/2608.23260/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2608.23260/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'