Feedback vertex sets of planar digraphs with fixed digirth
Let $fvs(G)$ denote the size of a minimum feedback vertex set of a digraph $G$. We study $fvs_g(n)$, which is the maximum $fvs(G)$ over all $n$-vertex planar digraphs $G$ of digirth $g$. We prove a planar-digraph analogue of the celebrated Lucchesi-Younger theorem showing that the minimum feedback vertex set is at most the maximum packing of a special type of directed cycles. As a corollary, we derive that $fvs_g(n)\le \frac{n-2}{g-2}$ for all $g\geq 3$. This improves all previously known upper bounds for $g \ge 4$, and for $g \ge 6$ it supersedes the best known upper bound of…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2605.12279
curl -X POST /api/v1/records/arxiv/2605.12279/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2605.12279/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'