An improved bound on the largest induced forests for triangle-free planar graphs
We proved that every planar triangle-free graph of order n has a subset of vertices that induces a forest of size at least (71n + 72)/128. This improves the earlier work of Salavatipour (2006). We also pose some questions regarding planar graphs of higher girth.
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Discrete Mathematics & Theoretical Computer Science
2010-01-01
|
| Series: | Discrete Mathematics & Theoretical Computer Science |
| Subjects: | |
| Online Access: | https://dmtcs.episciences.org/487/pdf |
| _version_ | 1797270179962421248 |
|---|---|
| author | Lukasz Kowalik Borut Luzar Riste Skrekovski |
| author_facet | Lukasz Kowalik Borut Luzar Riste Skrekovski |
| author_sort | Lukasz Kowalik |
| collection | DOAJ |
| description | We proved that every planar triangle-free graph of order n has a subset of vertices that induces a forest of size at least (71n + 72)/128. This improves the earlier work of Salavatipour (2006). We also pose some questions regarding planar graphs of higher girth. |
| first_indexed | 2024-04-25T02:00:10Z |
| format | Article |
| id | doaj.art-f436f1790c5f4812a0d6e5c3f6a045ce |
| institution | Directory Open Access Journal |
| issn | 1365-8050 |
| language | English |
| last_indexed | 2024-04-25T02:00:10Z |
| publishDate | 2010-01-01 |
| publisher | Discrete Mathematics & Theoretical Computer Science |
| record_format | Article |
| series | Discrete Mathematics & Theoretical Computer Science |
| spelling | doaj.art-f436f1790c5f4812a0d6e5c3f6a045ce2024-03-07T15:14:59ZengDiscrete Mathematics & Theoretical Computer ScienceDiscrete Mathematics & Theoretical Computer Science1365-80502010-01-01Vol. 12 no. 110.46298/dmtcs.487487An improved bound on the largest induced forests for triangle-free planar graphsLukasz Kowalik0Borut Luzar1Riste Skrekovski2Institute of Informatics [Warsaw]Faculty of Mathematics and Physics [Ljubljana]Faculty of Mathematics and Physics [Ljubljana]We proved that every planar triangle-free graph of order n has a subset of vertices that induces a forest of size at least (71n + 72)/128. This improves the earlier work of Salavatipour (2006). We also pose some questions regarding planar graphs of higher girth.https://dmtcs.episciences.org/487/pdfinduced forestforest numberdecycling number[info.info-dm] computer science [cs]/discrete mathematics [cs.dm] |
| spellingShingle | Lukasz Kowalik Borut Luzar Riste Skrekovski An improved bound on the largest induced forests for triangle-free planar graphs Discrete Mathematics & Theoretical Computer Science induced forest forest number decycling number [info.info-dm] computer science [cs]/discrete mathematics [cs.dm] |
| title | An improved bound on the largest induced forests for triangle-free planar graphs |
| title_full | An improved bound on the largest induced forests for triangle-free planar graphs |
| title_fullStr | An improved bound on the largest induced forests for triangle-free planar graphs |
| title_full_unstemmed | An improved bound on the largest induced forests for triangle-free planar graphs |
| title_short | An improved bound on the largest induced forests for triangle-free planar graphs |
| title_sort | improved bound on the largest induced forests for triangle free planar graphs |
| topic | induced forest forest number decycling number [info.info-dm] computer science [cs]/discrete mathematics [cs.dm] |
| url | https://dmtcs.episciences.org/487/pdf |
| work_keys_str_mv | AT lukaszkowalik animprovedboundonthelargestinducedforestsfortrianglefreeplanargraphs AT borutluzar animprovedboundonthelargestinducedforestsfortrianglefreeplanargraphs AT risteskrekovski animprovedboundonthelargestinducedforestsfortrianglefreeplanargraphs AT lukaszkowalik improvedboundonthelargestinducedforestsfortrianglefreeplanargraphs AT borutluzar improvedboundonthelargestinducedforestsfortrianglefreeplanargraphs AT risteskrekovski improvedboundonthelargestinducedforestsfortrianglefreeplanargraphs |