Kowalik–Lużar–Skrekovski conjecture for planar graphs of girth at least five
Kowalik–Lużar–Skrekovski conjecture for planar graphs of girth at least five
A feedback vertex set of a graph is a set such that is a forest. Let denote the minimum size of a feedback vertex set of . 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 is a planar graph of girth at least five on vertices, then
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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.