Finding a minimum clique cover is NP-hard, and its decision version is NP-complete.
It is possible to compute the clique cover number in perfect graphs in polynomial time.
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.
[4] Baker's technique can be used to provide a polynomial-time approximation scheme for the problem on planar graphs.