Nombre achromatique

Trouver ψ(G) est un problème d'optimisation. Le problème de décision pour le problème de coloration complète peut être exprimé ainsi :

INSTANCE : un graphe ${\displaystyle G=(S,A)}$ et un entier positif ${\displaystyle k}$

QUESTION : existe-t-il une partition de ${\displaystyle S}$ en au plus ${\displaystyle k}$ ensembles ${\displaystyle S_{1},S_{2},\ldots ,S_{k}}$ disjoints deux à deux, telle que chaque ${\displaystyle S_{i}}$ soit un ensemble indépendant pour ${\displaystyle G}$ et telle que pour chaque paire d'ensembles distincts ${\displaystyle S_{i},S_{j},S_{i}\cup S_{j}}$ ne soit pas un ensemble indépendant.

Déterminer le nombre achromatique est NP-difficile ; déterminer s'il est supérieur à un nombre donné est NP-complet, comme l'ont montré Yannakakis et Gavril en 1978 par une transformation depuis le problème minimum maximal matching. Le problème reste NP-complet même si on le restreint aux graphes qui sont le complément d'un graphe biparti (c’est-à-dire d'un graphe qui n'a pas d'ensemble indépendant de plus de deux sommets).

Le problème d'optimisation est approximable en ${\displaystyle O\left(|S|/{\sqrt {\log |S|}}\right)}$