---
tag: 36QKWMWENK
kind: concept
name: Complete coloring
aliases: [achromatic-number]
sources:
  - wikipedia: en:690736@r1368937158
    locator: Complete coloring
    note: adopted
    mention: wikipedia://en/690736
    sections: [Summary]
same_as:
  wikidata: Q3342988
  wikipedia: Complete coloring
inventory: [A18N9ESG8K]
---

## Summary

In graph theory, a **complete coloring** is a (proper) [[vertex coloring|0NCPXH194Y]] 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$.