The feedback vertex set bound for planar graphs of prescribed girth
Let be a finite simple planar graph of size and girth , 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 of satisfying
Equivalently, has an induced forest with at least 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
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.