The planar 3-path vertex cover conjecture

Let GG be a planar graph of order nn, and let ψ3(G)\psi_3(G) denote its 3-path vertex cover number.

Planar 3-path vertex cover conjecture.

ψ3(G)23n.\psi_3(G) \le \frac{2}{3}n.

This conjecture was first mentioned by Brešar et al. in 2011. Equality is attained by, for example, vertex-disjoint unions of octahedron graphs arranged in a planar way; the conjecture remains open in the source.

Sources & referencesView supporting material

Primary source

Csilla Bujtás, Marko Jakovac and Zsolt Tuza, “The k-path vertex cover: general bounds and chordal graphs”, arXiv:2105.02018 (2021).

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.