Kowalik–Lużar–Skrekovski conjecture for planar graphs of girth at least five

A feedback vertex set of a graph GG is a set SV(G)S\subseteq V(G) such that GSG-S is a forest. Let ϕ(G)\phi(G) denote the minimum size of a feedback vertex set of GG. The girth of a graph is the length of its shortest cycle, with girth infinity for an acyclic graph. Kowalik–Lużar–Skrekovski conjecture. If GG is a planar graph of girth at least five on nn vertices, then

ϕ(G)3n10.\phi(G)\leq\frac{3n}{10}.

The bound is tight because the dodecahedron attains it. The supplied text does not state a resolution of this conjecture; the source paper presents it as an active problem and develops improved bounds toward it.

Sources & referencesView supporting material

Primary source

Tom Kelly and Chun-Hung Liu, “Minimum Size of Feedback Vertex Sets of Planar Graphs of Girth at least Five”, arXiv:1603.04559 (2016).

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.