{"id":"arxiv/2607.13895","url":"https://arxiv.org/abs/2607.13895","tags":["math.CO","cs.DM"],"score":0,"title":"Feedback vertex sets in oriented graphs","domain":"math.CO","source":"arxiv","authors":["Simon Dreyer"],"reviews":0,"subject":"math.CO","summary":"For an oriented graph $G$, denote by $fvs(G)$ the minimum number of vertices whose deletion from $G$ makes it acyclic. We show that an oriented graph $G$ on $n$ vertices and $m$ arcs satisfies $fvs(G) \\le \\frac{2n+m+h}{9}$ where $h$ denotes the number of connected components of $G$ that belong to a special class of oriented graphs. This result has three consequences. First, when $G$ is planar, we obtain that $fvs(G) \\le \\frac{2n+m}{9}$. In particular, this implies that $fvs(G) \\le \\frac{5n-6}{9}$ for any planar oriented graph $G$, improving the best known upper bound of…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-07-15","reactions":{}}