The feedback vertex set bound for planar graphs of prescribed girth

About 11 years old · traced to

Let GG be a finite simple planar graph of size mm and girth gg, where the girth is the length of a shortest cycle. A feedback vertex set is a set of vertices whose removal leaves an acyclic graph.

Feedback vertex set conjecture for prescribed girth. There exists a feedback vertex set SS of GG satisfying

∣S∣≤mg.|S| \le \frac{m}{g}.

Equivalently, GG has an induced forest with at least ∣V(G)∣−mg|V(G)|-\frac{m}{g} vertices. The source presents this as a conjecture for planar graphs with given girth and provides no evidence of resolution.

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.