Achromatic number

In graph theory, complete coloring is the opposite of harmonious coloring in the sense that it is a vertex coloring in which every pair of colors appears on at least one pair of adjacent vertices. Equivalently, a complete coloring is minimal in the sense that it cannot be transformed into a proper coloring with fewer colors by merging pairs of color classes. The achromatic number ψ(G) of a graph G is the maximum number of colors possible in any complete coloring of G.

Finding ψ(G) is an optimization problem. The decision problem for complete coloring can be phrased as:

Determining the achromatic number is NP-hard; determining if it is greater than a given number is NP-complete, as shown by Yannakakis and Gavril in 1978 by transformation from the minimum maximal matching problem.

Note that any coloring of a graph with the minimum number of colors must be a complete coloring, so minimizing the number of colors in a complete coloring is just a restatement of the standard graph coloring problem.

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 ${\displaystyle O\left(|V|/{\sqrt {\log |V|}}\right)}$ approximation ratio.

...
Wikipedia