Complete coloring

Summary

In graph theory, a complete coloring is a (proper) 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 $\psi(G)$ of a graph $G$ is the maximum number of colors possible in any complete coloring of $G$.