The clique-transversal set problem in claw-free graphs with degree at most 4
The clique-transversal set problem is to find a minimum clique-transversal set of a graph. It has been proved that CTS problem is NP-hard for claw-free graphs. We give a polynomial-time algorithm for CTS in claw-free graphs with small degrees.
clique-transversal set problem claw-free graph graph algorithms clique polynomial time algorithm