Jones' Conjecture for planar graphs

Let GG be a planar graph. A cycle packing is a set of vertex-disjoint cycles in GG; let cp(G)\operatorname{cp}(G) denote its maximum size. A feedback vertex set is a set SS of vertices such that GSG-S is a forest; let fvs(G)\operatorname{fvs}(G) denote the minimum size of a feedback vertex set.

Jones' Conjecture. Every planar graph GG satisfies

fvs(G)2cp(G).\operatorname{fvs}(G)\leqslant 2\cdot\operatorname{cp}(G).

This conjecture concerns the relationship between cycle packing and feedback vertex sets, strengthening the general Erdős–Pósa-type bound for planar graphs. The source confirms the conjecture for subcubic planar graphs, but the general planar case remains open.

Sources & referencesView supporting material

Primary source

Marthe Bonamy, François Dross, Tomáš Masařík, Wojciech Nadara, Marcin Pilipczuk and Michał Pilipczuk, “Jones' Conjecture in subcubic graphs”, arXiv:1912.01570 (2019).

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.