Si vous disposez d'ouvrages ou d'articles de référence ou si vous connaissez des sites web de qualité traitant du thème abordé ici, merci de compléter l'article en donnant les références utiles à sa vérifiabilité et en les liant à la section « Notes et références ».
Soit G un graphe. On munit l'espace usuel à n dimensions d'une correspondance entre ses dimensions et les sommets de G. À toute cliqueK de G on peut associer une contrainte linéaire sur un vecteur x de l'espace, appelée contrainte de clique :
la somme des composantes de x correspondant aux sommets de la clique K doit être inférieure ou égale à 1.
Il découle directement des définitions que tout vecteur 0-1 est caractéristique d'un stable de G si et seulement il satisfait les contraintes de clique (en fait les cliques de taille 2 suffisent).
Que peut-on dire des vecteurs positifs fractionnaires (pas nécessairement entiers) satisfaisant les contraintes de clique, appartiennent-ils au polytope des stables de G ?
La réponse est non puisque, si G est un cycle impair (différent du triangle), on obtient un contre-exemple avec le vecteur 1/2.
Lien avec les graphes parfaits
Václav Chvátal a montré que les vecteurs satisfaisant les contraintes de clique sont précisément ceux du polytope si et seulement si G est parfait. En d'autres termes, les hyperplans définis par les contraintes de cliques décrivent alors le polytope.
Bibliographie
Cette section est vide, insuffisamment détaillée ou incomplète. Votre aide est la bienvenue ! Comment faire ?
Notes et références
Cette section est vide, insuffisamment détaillée ou incomplète. Votre aide est la bienvenue ! Comment faire ?