Akiyama–Watanabe–Albertson–Haas conjecture on induced forests in bipartite planar graphs
Akiyama–Watanabe–Albertson–Haas conjecture on induced forests in bipartite planar graphs
Let be a finite simple bipartite planar graph of order . An induced forest is a vertex-induced subgraph of that is a forest.
Akiyama–Watanabe–Albertson–Haas conjecture. Every bipartite planar graph of order admits an induced forest of order at least
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.
Sources & referencesView supporting material
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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.