The feedback vertex set bound for planar graphs of prescribed girth

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

Smg.|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.

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

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.