Journal of Combinatorics

Volume 8 (2017)

Number 1

Induced forests in bipartite planar graphs

Pages: 93 – 166

DOI: https://dx.doi.org/10.4310/JOC.2017.v8.n1.a5

Authors

Yan Wang (School of Mathematics, Georgia Institute of Technology, Atlanta, Ga., U.S.A.)

Qiqin Xie (School of Mathematics, Georgia Institute of Technology, Atlanta, Ga., U.S.A.)

Xingxing Yu (School of Mathematics, Georgia Institute of Technology, Atlanta, Ga., U.S.A.)

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.

Keywords

induced forest, planar bipartite graph, discharging method

2010 Mathematics Subject Classification

05C05, 05C10, 05C30

Published 2 December 2016