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...
| Päätekijät: | , |
|---|---|
| Muut tekijät: | |
| Aineistotyyppi: | Artikkeli |
| Kieli: | en_US |
| Julkaistu: |
European Mathematical Information Service (EMIS)
2015
|
| Linkit: | http://hdl.handle.net/1721.1/98410 |