Small feedback vertex sets in planar digraphs (Q528978): Difference between revisions

Summary: Let \(G\) be a directed planar graph on \(n\) vertices, with no directed cycle of length less than \(g\geq 4\). We prove that \(G\) contains a set \(X\) of vertices such that \(G-X\) has no directed cycle, and \(|X|\leq \tfrac{5n-5}9\) if \(g=4\), \(|X|\leq \tfrac{2n-5}4\) if \(g=5\), and \(|X|\leq \tfrac{2n-6}{g}\) if \(g\geq 6\). This improves recent results of \textit{N. Golowich} and \textit{D. Rolnick} [Electron. J. Comb. 22, No. 3, Research Paper P3.7, 9 p. (2015; Zbl 1325.05060)].