Small feedback vertex sets in planar digraphs (Q528978)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Small feedback vertex sets in planar digraphs |
scientific article |
Statements
Small feedback vertex sets in planar digraphs (English)
0 references
18 May 2017
0 references
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)].
0 references
planar digraphs
0 references
digirth
0 references
feedback vertex sets
0 references