Induced Forests in Bipartite Planar Graphs

2016/04/30 by Yan Wang, Wang, Yan, Qiqin Xie +3
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #math.CO

paper · pdf · doi:10.48550/arxiv.1605.00047

arxiv created 2016/04/30 · openalex publication_date 2016/04/30 · arxiv updated 2016/05/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Akiyama and Watanabe conjectured that every simple planar bipartite graph on n vertices contains an induced forest on at least 5n/8 vertices. We apply the discharging method to show that every simple bipartite planar graph on n vertices contains an induced forest on at least \lceil (4n+3)/7 \rceil vertices.

Related

• Large induced forests in planar graphs with girth 4 or 5
• A better bound on the largest induced forests in triangle-free planar graphs
• Fractional vertex-arboricity of planar graphs
• Forest Cuts in Sparse Graphs
• Partitioning planar graphs without 4-cycles and 6-cycles into a forest and a disjoint union of paths