Akiyama–Watanabe–Albertson–Haas conjecture on induced forests in bipartite planar graphs

About 11 years old · traced to

Let GG be a finite simple bipartite planar graph of order nn. An induced forest is a vertex-induced subgraph of GG that is a forest.

Akiyama–Watanabe–Albertson–Haas conjecture. Every bipartite planar graph of order nn admits an induced forest of order at least

5n8.\frac{5n}{8}.

This strengthens the general lower-bound problem for planar graphs by imposing bipartiteness and seeking a larger induced forest. The source states the conjecture but gives no resolution; partial lower bounds and related results are discussed.

References

Primary source

François Dross, Mickael Montassier and Alexandre Pinlou, “A lower bound on the order of the largest induced forest in planar graphs with high girth”, arXiv:1504.01949 (2015).

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.