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...
| Principais autores: | , |
|---|---|
| Outros Autores: | |
| Formato: | Artigo |
| Idioma: | en_US |
| Publicado em: |
European Mathematical Information Service (EMIS)
2015
|
| Acesso em linha: | http://hdl.handle.net/1721.1/98410 |
| _version_ | 1826203871636094976 |
|---|---|
| author | Golowich, Noah Rolnick, David S. |
| author2 | Massachusetts Institute of Technology. Department of Mathematics |
| author_facet | Massachusetts Institute of Technology. Department of Mathematics Golowich, Noah Rolnick, David S. |
| author_sort | Golowich, Noah |
| collection | MIT |
| description | 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. |
| first_indexed | 2024-09-23T12:44:36Z |
| format | Article |
| id | mit-1721.1/98410 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T12:44:36Z |
| publishDate | 2015 |
| publisher | European Mathematical Information Service (EMIS) |
| record_format | dspace |
| spelling | mit-1721.1/984102022-10-01T10:50:27Z Acyclic Subgraphs of Planar Digraphs Golowich, Noah Rolnick, David S. Massachusetts Institute of Technology. Department of Mathematics Rolnick, David S. 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. 2015-09-08T18:58:24Z 2015-09-08T18:58:24Z 2015-07 2014-08 Article http://purl.org/eprint/type/JournalArticle 1077-8926 http://hdl.handle.net/1721.1/98410 Golowich, Noah, and David Rolnick. "Acyclic Subgraphs of Planar Digraphs." The Electronic Journal of Combinatorics 22(3) (2015), #P3.7. en_US http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i3p7/pdf Electronic Journal of Combinatorics Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. application/pdf European Mathematical Information Service (EMIS) European Mathematical Information Service (EMIS) |
| spellingShingle | Golowich, Noah Rolnick, David S. Acyclic Subgraphs of Planar Digraphs |
| title | Acyclic Subgraphs of Planar Digraphs |
| title_full | Acyclic Subgraphs of Planar Digraphs |
| title_fullStr | Acyclic Subgraphs of Planar Digraphs |
| title_full_unstemmed | Acyclic Subgraphs of Planar Digraphs |
| title_short | Acyclic Subgraphs of Planar Digraphs |
| title_sort | acyclic subgraphs of planar digraphs |
| url | http://hdl.handle.net/1721.1/98410 |
| work_keys_str_mv | AT golowichnoah acyclicsubgraphsofplanardigraphs AT rolnickdavids acyclicsubgraphsofplanardigraphs |