Let $G$ be a directed planar graph on $n$ vertices, with no directed cycle of length less than $g\ge 4$. We prove that $G$ contains a set $X$ of vertices such that $G-X$ has no directed cycle, and $|X|\le \tfrac{5n-5}9$ if $g=4$, $|X|\le \tfrac{2n-5}4$ if $g=5$, and $|X|\le \tfrac{2n-6}{g}$ if $g\ge 6$. This improves recent results of Golowich and Rolnick.
@article{10_37236_6252,
author = {Louis Esperet and Laetitia Lemoine and Fr\'ed\'eric Maffray},
title = {Small feedback vertex sets in planar digraphs},
journal = {The electronic journal of combinatorics},
year = {2017},
volume = {24},
number = {2},
doi = {10.37236/6252},
zbl = {1361.05058},
url = {http://geodesic.mathdoc.fr/articles/10.37236/6252/}
}
TY - JOUR
AU - Louis Esperet
AU - Laetitia Lemoine
AU - Frédéric Maffray
TI - Small feedback vertex sets in planar digraphs
JO - The electronic journal of combinatorics
PY - 2017
VL - 24
IS - 2
UR - http://geodesic.mathdoc.fr/articles/10.37236/6252/
DO - 10.37236/6252
ID - 10_37236_6252
ER -
%0 Journal Article
%A Louis Esperet
%A Laetitia Lemoine
%A Frédéric Maffray
%T Small feedback vertex sets in planar digraphs
%J The electronic journal of combinatorics
%D 2017
%V 24
%N 2
%U http://geodesic.mathdoc.fr/articles/10.37236/6252/
%R 10.37236/6252
%F 10_37236_6252
Louis Esperet; Laetitia Lemoine; Frédéric Maffray. Small feedback vertex sets in planar digraphs. The electronic journal of combinatorics, Tome 24 (2017) no. 2. doi: 10.37236/6252
