Large induced acyclic and outerplanar subgraphs of 2-outerplanar graph
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2017
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866915870159142912 |
|---|---|
| author | Borradaile, Glencora Le, Hung Sherman-Bennett, Melissa |
| author_facet | Borradaile, Glencora Le, Hung Sherman-Bennett, Melissa |
| contents | Albertson and Berman conjectured that every planar graph has an induced forest on half of its vertices. The best known lower bound, due to Borodin, is that every planar graph has an induced forest on two fifths of its vertices. In a related result, Chartran and Kronk, proved that the vertices of every planar graph can be partitioned into three sets, each of which induce a forest.
We show tighter results for 2-outerplanar graphs. We show that every 2-outerplanar graph has an induced forest on at least half the vertices by showing that its vertices can be partitioned into two sets, each of which induces a forest. We also show that every 2-outerplanar graph has an induced outerplanar graph on at least two-thirds of its vertices, assuming that the connected components of the inner layer are two-connected. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_1711_00212 |
| institution | arXiv |
| publishDate | 2017 |
| record_format | arxiv |
| spellingShingle | Large induced acyclic and outerplanar subgraphs of 2-outerplanar graph Borradaile, Glencora Le, Hung Sherman-Bennett, Melissa Combinatorics 05C10 Albertson and Berman conjectured that every planar graph has an induced forest on half of its vertices. The best known lower bound, due to Borodin, is that every planar graph has an induced forest on two fifths of its vertices. In a related result, Chartran and Kronk, proved that the vertices of every planar graph can be partitioned into three sets, each of which induce a forest. We show tighter results for 2-outerplanar graphs. We show that every 2-outerplanar graph has an induced forest on at least half the vertices by showing that its vertices can be partitioned into two sets, each of which induces a forest. We also show that every 2-outerplanar graph has an induced outerplanar graph on at least two-thirds of its vertices, assuming that the connected components of the inner layer are two-connected. |
| title | Large induced acyclic and outerplanar subgraphs of 2-outerplanar graph |
| topic | Combinatorics 05C10 |
| url | https://arxiv.org/abs/1711.00212 |