Nombre domatique
# Nombre domatique

En théorie des graphes, le nombre domatique d'un graphe est son nombre maximum d'ensembles dominants disjoints deux à deux. Le problème du nombre domatique est de déterminer, en fonction d'un graphe G et d'un entier naturel k, si le nombre domatique de G est supérieur ou égal à k. C'est un problème NP-complet.

## Exemple

Dans le graphe ci-contre, les trois ensembles de sommets (associés à chaque couleur) sont disjoints deux à deux, et dominants (par exemple pour l'ensemble jaune : tout sommet est soit jaune, soit voisin d'un jaune). Le nombre domatique du graphe vaut donc au moins 3 (en fait, il est exactement égal à 3).

## Définitions équivalentes

Le nombre domatique de G est le plus grand entier n pour lequel il existe une partition de l'ensemble des sommets en n ensembles dominants.

Le problème du nombre domatique pour G et k revient à déterminer s'il existe k ensembles dominants disjoints deux à deux.

## Complexité

Le problème du nombre domatique a été prouvé NP-complet par réduction mutuelle avec le problème 3SAT.

