Complete coloring

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.

For any fixed k, it is possible to determine whether the achromatic number of a given graph is at least k, in linear time.

[5] For complements of trees, the achromatic number can be computed in polynomial time.

[3] The achromatic number of an n-dimensional hypercube graph is known to be proportional to

Complete coloring of the Clebsch graph with 8 colors. Every pair of colors appears on at least one edge. No complete coloring with more colors exists: in any 9-coloring some color would appear only at one vertex, and there would not be enough neighboring vertices to cover all pairs involving that color. Therefore, the achromatic number of the Clebsch graph is 8.