b-cliques en théorie des graphes
Bonjour,
Je cherche un contre exemple ou une preuve pour l'assertion: "Dans un graphe $G=(V,E)$, toute b-clique s'écrit comme la somme de b 1-cliques".
Pour rappel, une b-clique d'un graphe $G=(V,E)$ est une application $\omega :V\rightarrow \mathbb{N}$ telle que pour tout stable $I$ on ait la propriété $$\displaystyle \omega (I) = \sum_{x\in I}\omega(x)\leq b$$
La réciproque est vraie: si on dispose de b 1-cliques, il suffit de les sommer pour obtenir une b-clique.
Merci de votre aide!
Je cherche un contre exemple ou une preuve pour l'assertion: "Dans un graphe $G=(V,E)$, toute b-clique s'écrit comme la somme de b 1-cliques".
Pour rappel, une b-clique d'un graphe $G=(V,E)$ est une application $\omega :V\rightarrow \mathbb{N}$ telle que pour tout stable $I$ on ait la propriété $$\displaystyle \omega (I) = \sum_{x\in I}\omega(x)\leq b$$
La réciproque est vraie: si on dispose de b 1-cliques, il suffit de les sommer pour obtenir une b-clique.
Merci de votre aide!
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
On se prend $G=(V,E)$ avec $V=\{a,b,c,d,e\}$ et $E=\{(a,b),(b,c),(c,d),(d,e),(e,a)\}$ (un pentagone quoi).
Alors les 1-cliques ont au plus 2 sommets à 1, nécessairement adjacents.
Or si on prend la 3-clique $\omega(a)=2,~\omega(b)=2,~\omega(c)=1,~\omega(d)=1,~\omega(e)=1$, elle n'est clairement pas la somme de trois 1-cliques, car une telle somme aurait la somme de ses valeurs à au plus 6, alors que ma clique a une somme à 7!
Voilà!