Induced forests in bipartite planar graphs

Yan Wang, Qiqin Xie, Xingxing Yu · Journal of Combinatorics · 2016

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.

Read the paper · More papers on PaperTik