Jones' Conjecture for planar graphs
Statement
Let be a planar graph. A cycle packing is a set of vertex-disjoint cycles in ; let denote its maximum size. A feedback vertex set is a set of vertices such that is a forest; let denote the minimum size of a feedback vertex set.
Jones' Conjecture. Every planar graph satisfies
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.
Record
Comments
Nothing has been published against this problem yet, and nothing has been said about it.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.