Akiyama–Watanabe conjecture on induced forests in bipartite planar graphs

Let GG be a simple bipartite planar graph. Write G=V(G)|G|=|V(G)|, and let a(G)a(G) denote the maximum number of vertices in an induced forest of GG. Akiyama–Watanabe conjecture.

a(G)5G8.a(G) \geq \frac{5|G|}{8}.

The conjecture was proposed in 1987. The paper proves the weaker lower bound a(G)(4G+3)/7a(G)\geq \lceil(4|G|+3)/7\rceil, so the stated 5G/85|G|/8 bound is not resolved by the supplied text.

Sources & referencesView supporting material

Primary source

Yan Wang, Qiqin Xie and Xingxing Yu, “Induced Forests in Bipartite Planar Graphs”, arXiv:1605.00047 (2016).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.