The chordal graph k-path vertex cover conjecture

Let k3k\ge 3, let GG be a chordal graph with clique number ω\omega, and write n=V(G)n=|V(G)|. Let ψk(G)\psi_k(G) denote the minimum size of a vertex set meeting every path on kk vertices in GG.

Chordal graph k-path vertex cover conjecture.

ψk(G)ω1ω+k2n.\psi_k(G) \le \frac{\omega-1}{\omega+k-2}n.

The authors present this as a hoped-for improvement to some of the paper's bounds for chordal graphs. No resolution is given in the supplied text.

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.