Exercice 5 - ensemble stable et $k$-coloration

Soit $G = (S, A)$ un graphe, $k$ une constante strictement positive. On s'intéresse à la $k$-colorabilité du graphe $G$ (i.e. peut-on colorier le graphe $G$ avec $k$ couleurs ?). Nous allons créer un graphe $G^\prime = (S^\prime, A^\prime)$ à partir de $G$ en procédant de la façon suivante :

• A chaque sommet $s$ de $G$, on associe $k$ sommets de $G^\prime$, notés $\{(s, 1), \ldots, (s, k)\}$, tous reliés entre eux par des arêtes.
• Pour chaque arête $\{e, e^\prime\}$ de $G$, et chaque couleur $j$, on relie dans $G^\prime$ les sommets $(e, j)$ et $(e^\prime, j)$. Notez bien que comme les sommets sont des couples, les arêtes sont des paires de couples.

Plus formellement,

• 
  
  $$S^\prime = \{(s, j) \vert s \in S, j \in \{1, \ldots, k\}\}$$
  
  
  est un ensemble de couples (sommet de $G$/couleur).
• 
  
  $$A^\prime = A_1 \cup A_2$$
  
  
  avec
  
  $$A_1 = \{\{(s, j), (s, j^\prime)\} \vert s \in S, 1 \leq j < j^\prime \leq k\}$$
  
  
  un ensemble d'arêtes formant $\vert S\vert$ sous-graphes complets de $k$ sommets et
  
  $$A_2 = \{ \{(e, j), (e^\prime, j)\} \vert \{e, e^\prime\} \in A, j \in \{1, \ldots, k \}\}$$
  
  
  un ensemble d'arêtes interconnectant ces sous-graphes.

Le but de cet exercice est de montrer qu'en trouvant un ensemble stable de $\vert S\vert$ sommets dans $G^\prime$, on trouve aussi une $k$-coloration de $G$.

1. Soit $G$ le graphe de l'exercice précédent, on pose $k = 3$. Représentez graphiquement $G^\prime$.
2. Donnez une définition en français (avec des mots) de ce qu'est un ensemble stable.
3. Ce problème (existe-t-il un ensemble stable de $\vert S\vert$ sommets dans $G^\prime$ ?) est-il NP-Complet ?
4. Donnez un ensemble stable de $5$ sommets dans ce graphe.
5. Utilisez cet ensemble stable pour déterminer une $3$-coloration de $G$.
6. Démontrez de façon formelle et avec le plus de rigueur possible que, étant donné un graphe $G$ arbitraire, un nombre $k > 0$, $G$ est $k$-colorable si et seulement s'il existe un ensemble stable de $\vert S\vert$ sommets dans $G^\prime$.