Acyclic Subgraphs of Planar Digraphs

  • Noah Golowich
  • David Rolnick
Keywords: Acyclic set, Chromatic number, Digraph, Planar graph, Directed cut

Abstract

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$.
Published
2015-07-01
Article Number
P3.7