Algorithms
For any fixed k, it is possible to determine whether the achromatic number of a given graph is at least k, in linear time.
The optimization problem permits approximation and is approximable within a approximation ratio.
Read more about this topic: Complete Coloring