Albertson–Berman's planar graph feedback vertex set conjecture

Let GG be a simple undirected planar graph on nn vertices. A feedback vertex set is a set of vertices whose deletion leaves an acyclic graph, and fvs(G)fvs(G) denotes its minimum size.

Albertson–Berman's conjecture.

fvs(G)n2.fvs(G)\leq \frac{n}{2}.

This is presented as a widely open strengthening of the independent-set consequence of the Four Color Theorem.

Sources & referencesView supporting material

Primary source

Simon Dreyer, Alexandre Pinlou and Petru Valicov, “Feedback vertex sets of planar digraphs with fixed digirth”, arXiv:2605.12279 (2026).

Additional references

7 papers in this index state this conjecture (2013–2026). The statement above is taken from the most recent of them; the others are arXiv:2601.04637, arXiv:2506.10471, arXiv:2104.12030, arXiv:1504.01949, arXiv:1504.06726, arXiv:1309.4713.

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.