pairs of adjacent vertices) together with singleton sets for the remaining unmatched vertices. The number of cliques equals the number of vertices minus the number of matched pairs. Therefore, in triangle-free graphs, the minimum clique cover can be found by using an algorithm for maximum matching. The optimum partition into cliques can also be found in polynomial time for graphs of bounded clique-width. These include, among other graphs, the cographs and distance-hereditary graphs, which are both also classes of perfect graphs. The clique cover problem remains NP-complete on some other special classes of graphs, including the cubic planar graphs and unit disk graphs. Approximation The same hardness of approximation results that are known for graph coloring also apply to clique cover. Therefore, unless P = NP, there can be no polynomial time approximation algorithm for any that, on -vertex graphs, achieves an approximation ratio better than . In graphs where every vertex has at most three neighbors, the clique cover remains NP-hard, and there is a constant such that it is NP-hard to approximate with approximation ratio or better. Nevertheless, in polynomial time it is possible to find an approximation with ratio 5/4. That is, this approximation algorithm finds a clique cover whose number of cliques is no more than 5/4 times the optimum. Baker's technique can be used to provide a polynomial-time approximation scheme for the problem on planar graphs. Related problems The related clique edge cover problem concerns partitioning the edges of a graph, rather than the vertices, into subgraphs induced by cliques. It is also NP-complete. References Graph theory objects NP-complete problems Computational problems in graph theory