{"id":"arxiv/2601.04637","url":"https://arxiv.org/abs/2601.04637","tags":["math.CO","cs.DM"],"score":0,"title":"Large induced forests in planar multigraphs","domain":"math.CO","source":"arxiv","authors":["Mikhail Makarov"],"reviews":0,"subject":"math.CO","summary":"For a graph $G$, denote by $a(G)$ the number of vertices in the largest induced forest in $G$. The Albertson-Berman conjecture, which has been open since 1979, states that $a(G) \\geq \\frac{n}{2}$ for every simple planar graph $G$ on $n$ vertices. We show that the version of this problem for multigraphs (allowing parallel edges) is easily reduced to the problem about the independence number of simple planar graphs. Specifically, we prove that $a(M) \\geq \\frac{n}{4}$ for every planar multigraph $M$ and that this lower bound is tight. Then, we study the case when the number of pairs of vertices…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-01-08","reactions":{}}