Akiyama–Watanabe conjecture on induced forests in bipartite planar graphs

At least 9 years old · documented by

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)≥5∣G∣8.a(G) \geq \frac{5|G|}{8}.

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

References

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.