Large Induced Forests in Triangle-Free Planar Graphs |
| |
Authors: | Mohammad R Salavatipour |
| |
Institution: | (1) Department of Computing Science, University of Alberta, Edmonton Alberta, T6G 2E8, Canada |
| |
Abstract: | Given a planar graph G, what is the largest subset of vertices of G that induces a forest? Albertson and Berman 2] conjectured that every planar graph has an induced subgraph on at least half of the vertices that is a forest. For bipartite planar graphs, Akiyama and Wanatabe 1] conjectured that there is always an induced forest of size at least 5n/8. Here we prove that every triangle-free (and therefore every bipartite) planar graph on n vertices has an induced forest of size at least (17n+24)/32. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|