La correction d'Exercice sur la coloration d'arête et la coloration de sommets (Recherche opérationnelle)





a) oui , on crée un graphe auxiliaire G' à partir du graphe de départ G.
pour chaque arête de G , on crée un sommet dans G' .On relie ensuite 2 sommets de G' si les arêtes correspondantes sont adjacentes dans G.
De cette façon , une coloration d’arêtes dans le graphe G correspond à une coloration de sommets dans G' et inversement.


b) Non , par exemple on ne peut pas appliquer la transformation inverse à ce graphe :