title: Nombre domatique
text: # 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.
  
  