Acyclic subgraphs of planar digraphs (Q2517654)

Summary: An acyclic set in a digraph is a set of vertices that induces an acyclic subgraph. In [Brooks-type results for coloring of digraphs. Burnaby, British Columbia: Simon Fraser University (PhD Thesis) (2011)], \textit{A. 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\).