Acyclic Subgraphs of Planar Digraphs

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 l...

Full description

Bibliographic Details
Main Authors: Golowich, Noah, Rolnick, David S.
Other Authors: Massachusetts Institute of Technology. Department of Mathematics
Format: Article
Language:en_US
Published: European Mathematical Information Service (EMIS) 2015
Online Access:http://hdl.handle.net/1721.1/98410