Akiyama–Watanabe–Albertson–Hass conjecture for bipartite planar graphs

Let GG be a bipartite planar graph, and let fvs(G)\mathrm{fvs}(G) denote the minimum size of a feedback vertex set of GG, that is, a vertex set whose deletion leaves a forest.

Akiyama–Watanabe–Albertson–Hass conjecture. Every bipartite planar graph GG satisfies

fvs(G)≤3v(G)8.\mathrm{fvs}(G)\leq \frac{3v(G)}{8}.

The source describes this as an open conjecture. The current best bound given there is fvs(G)≤(3v(G)−3)/7\mathrm{fvs}(G)\leq (3v(G)-3)/7, which does not establish the conjectured bound.

References

Primary source

Sirui Chen, Jiaao Li and Zhouningxin Wang, “Frustration index of a signed planar graph and the feedback vertex set”, arXiv:2607.17983 (2026).

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.