Small feedback vertex sets in planar digraphs (Q528978): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Set profile property. |
||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank |
Revision as of 01:32, 5 March 2024
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