Bibm@th

Sous-graphe

  Si G est un graphe dont les sommets sont l'ensemble S et les arêtes sont l'ensemble A, et si S' est une partie de S, on appelle sous-graphe de S formé à partir de S' le graphe dont les sommets sont les éléments de S' et les arêtes sont les éléments de A reliant deux sommets de S'. Par exemple, dans l'exemple suivant, on a tracé un graphe et sous-graphe formé à partir des sommets A,B,C,D :
  Un sous-graphe est dit stable s'il ne comporte aucune arête. Colorier un graphe revient à chercher des sous-graphes stables dans un graphe.