Cliques, Stables, Coloration

Deux sous graphes particuliers ont une importance toute particulière dans le monde de la théorie des graphes : les cliques et les stables. Comme nous allons le voir immédiatement, ces deux notions sont totalement opposées.



Remarque : Un sommet isolé est à la fois une clique et un stable. Par extension, l'ensemble des sommets d'un stable (respectivement une clique) de $G$ sera nommé un stable (respectivement, une clique).

Cette dernière notation est lié au problème classique de coloration d'une carte. Soit une carte géographique représentant plusieurs pays. On souhaite colorier chaque pays de manière à ce qu'il n'ait pas la même couleur que chacun de ses voisins. Ce problème peut être résolu en cherchant une partition en stables du graphe obtenu en associant chaque pays à un sommet et chaque arc à une frontière commune entre 2 pays. Il suffit alors d'associer une couleur à chaque stable obtenu. Remarque : on essaye le plus souvent de déterminer le nombre minimal de couleurs nécessaires. Il a été démontré que l'on peut toujours colorier un graphe planaire avec, au plus, 3 couleurs.