The clique-transversal set problem in claw-free graphs with degree at most 4

A clique of a graph G is defined as a complete subgraph maximal under inclusion and having at least two vertices. A clique-transversal set D of G is a subset of vertices of G such that D meets all cliques of G. The clique-transversal set problem is to find a minimum clique-transversal set of G. In this paper we present a polynomial time algorithm for the clique-transversal set problem on claw-free graphs with degree at most 4.