An acyclic set in a digraph is a set of vertices that induces an acyclic subgraph. In 2011, Harutyunyan conjectured that every planar digraph on $n$ vertices without directed 2-cycles possesses an acyclic set of size at least $3n/5$. We prove this conjecture for digraphs where every directed cycle has length at least 8. More generally, if $g$ is the length of the shortest directed cycle, we show that there exists an acyclic set of size at least $(1 - 3/g)n$.
@article{10_37236_4596,
author = {Noah Golowich and David Rolnick},
title = {Acyclic subgraphs of planar digraphs},
journal = {The electronic journal of combinatorics},
year = {2015},
volume = {22},
number = {3},
doi = {10.37236/4596},
zbl = {1325.05060},
url = {http://geodesic.mathdoc.fr/articles/10.37236/4596/}
}
TY - JOUR
AU - Noah Golowich
AU - David Rolnick
TI - Acyclic subgraphs of planar digraphs
JO - The electronic journal of combinatorics
PY - 2015
VL - 22
IS - 3
UR - http://geodesic.mathdoc.fr/articles/10.37236/4596/
DO - 10.37236/4596
ID - 10_37236_4596
ER -
%0 Journal Article
%A Noah Golowich
%A David Rolnick
%T Acyclic subgraphs of planar digraphs
%J The electronic journal of combinatorics
%D 2015
%V 22
%N 3
%U http://geodesic.mathdoc.fr/articles/10.37236/4596/
%R 10.37236/4596
%F 10_37236_4596
Noah Golowich; David Rolnick. Acyclic subgraphs of planar digraphs. The electronic journal of combinatorics, Tome 22 (2015) no. 3. doi: 10.37236/4596
