Approximation algorithms for clique transversals on some graph classes

• A 3-approximation algorithm for unweighted line graphs.
• A 4-approximation algorithm for weighted line graphs.
• A 3-approximation algorithm for planar graphs.
• A ⌈(Δ(G)+1)/2⌉⌈(Δ(G)+1)/2⌉-approximation algorithm for bounded degree graphs.

Given a graph G=(V,E)G=(V,E) a clique is a maximal subset of pairwise adjacent vertices of V of size at least 2. A clique transversal is a subset of vertices that intersects the vertex set of each clique of G  . Finding a minimum-cardinality clique transversal is NP-hard for the following classes: planar, line and bounded degree graphs. For line graphs we present a 3-approximation for the unweighted case and a 4-approximation for the weighted case with nonnegative weights; a ⌈(Δ(G)+1)/2⌉⌈(Δ(G)+1)/2⌉-approximation for bounded degree graphs and a 3-approximation for planar graphs.