Csilla Bujtas: The k-path vertex cover problem

Abstract. For an integer k >2, a k-path vertex cover of a graph G is a set T of vertices such that G-T does not contain a subgraph isomorphic to P_k. After reviewing some earlier results, we first prove general estimates on the corresponding graph parameter and then, we consider the problem on chordal graphs and planar graphs.