Coloration des sommets

Soit G = (V, E) un graphe. Un sous-ensemble S de V est un stable s'il ne comprend que des sommets non adjacents deux à deux. Le cardinal du plus grand stable est le nombre de stabilité de G; on le note a(G). La coloration des sommets d'un graphe consiste à affecter à tous les sommets de ce graphe une couleur de telle sorte que deux sommets adjacents ne portent pas la même couleur. Une coloration avec k couleurs est donc une partition de l'ensemble des sommets en k stables. Le nombre chromatique du graphe G, noté g(G), est le plus petit entier k pour lequel il existe une partition de V en k sous-ensembles stables. Sur le graphe ci-contre, on a eu besoin de trois couleurs pour colorer les sommets de sorte que deux sommets adjacents ont des couleurs différentes. On a donc trois stables: {1, 2}, {3, 5} et {4}. On ne peut pas utiliser moins de couleurs, à cause des cliques 1-4-5 et 1-3-4. Remarquons enfin que le sommet 2 aurait pu aussi être vert. La coloration minimale n'est donc pas forcément unique.

Une coloration des sommets

Encadrement du nombre chromatique

Majoration

1. g(G) r + 1, où r est le plus grand degré de ses sommets.
   Preuve: Soit un graphe et r le degré maximum de ses sommets. Donnons-nous une palette de (r + 1) couleurs. Pour chaque sommet du graphe on peut tenir le raisonnement suivant: ce sommet est adjacent à r sommets au plus, et le nombre de couleurs déjà utilisées pour colorer ces sommets est donc inférieur ou égal à r. Il reste donc au moins une couleur non utilisée dans la palette, avec laquelle nous pouvons colorer notre sommet.

2. g(G) n + 1 - a(G)
   Preuve: Considérons S un stable de V de cardinal a(G): une coloration possible des sommets consiste à colorer les sommets de S d'une même couleur et les n-a(G) autres sommets de couleurs toutes différentes. On en déduit que g(G) 1+(n-a(G)).

Minoration

1. Le nombre chromatique d'un graphe est supérieur ou égal à celui de chacun de ses sous-graphes.
   Preuve: Ce résultat découle de la définition même du nombre chromatique.

2. g(G) w(G)
   Preuve: Pusique, par définition, dans une clique d'ordre m, tous les sommets sont adjacents entre eux, il faudra m couleurs. Donc, forcément, le nombre chromatique du graphe sera supérieur ou égal à l'ordre de sa plus grande clique.

Algorithme de coloration de Welsh et Powell Cet algorithme couramment utilisé permet d'obtenir une assez bonne coloration d'un graphe, c'est-à-dire une coloration n'utilisant pas un trop grand nombre de couleurs. Cependant il n'assure pas que le nombre de couleurs utilisé soit minimum (et donc égal au nombre chromatique du graphe). Étape 1 Classer les sommets du graphe dans l'ordre décroissant de leur degré, et attribuer à chacun des sommets son numéro d'ordre dans la liste obtenue. Étape 2 En parcourant la liste dans l'ordre, attribuer une couleur non encore utilisée au premier sommet non encore coloré, et attribuer cette même couleur à chaque sommet non encore coloré et non adjacent à un sommet de cette couleur. Étape 3 S'il reste des sommets non colorés dans le graphe, revenir à l'étape 2. Sinon, la coloration est terminée.

Exercices

Exercice 1

Tout graphe contenant un triangle (K₃) ne peut pas être coloré en moins de trois couleurs.

1. Construire un graphe sans K₃ qui nécessite également trois couleurs.
2. Comment, à partir du graphe précédent, construire un graphe sans K₄ nécessitant 4 couleurs ?
3. Un graphe sans K₅ nécessitant 5 couleurs ?

Déterminez le nombre chromatique de ce graphe.

Exercice 3

Sept élèves, désignés par A, B, C, D, E, F et G, se sont rendus à la bibliothèque aujourd'hui. Le tableau suivant précise «qui a rencontré qui» (la bibliothèque étant petite, deux élèves présents au même moment se rencontrent nécessairement...).

De combien de places assises doit disposer la bibliothèque pour que chacun ait pu travailler correctement au cours de cette journée?

Exercice 4

A, B, C, D, E, F, G et H désignent huit poissons. Dans le tableau ci-dessous, une croix signifie que les poissons ne peuvent pas cohabiter dans un même aquarium:

Quel nombre minimum d'aquariums faut-il?

Exercice 5

Un lycée doit organiser les horaires des examens. On suppose qu'il y a 7 épreuves à planifier, correspondant aux cours numérotés de 1 à 7 et que les paires de cours suivantes ont des étudiants communs: 1 et 2, 1 et 3, 1 et 4, 1 et 7, 2 et 3, 2 et 4, 2 et 5, 2 et 7, 3 et 4, 3 et 6, 3 et 7, 4 et 5, 4 et 6, 5 et 6, 5 et 7 et enfin 6 et 7.
Comment organiser ces épreuves de façon qu'aucun étudiant n'ait à passer deux épreuves en même temps et cela sur une durée miminale?

Exercice 6

Sept agences de voyage romaines proposent des visites de monuments et lieux touristiques: le Colisée, le Forum romain, le musée du Vatican et les thermes de Caracalas. Un même lieu ne peut être visité par plusieurs groupes de compagnies différentes le même jour.
La première Compagnie fait visiter uniquement le Colisée; la seconde le Colisée et le musée du Vatican; la troisième les thermes de Caracalas; la quatrième le musée du Vatican et les thermes de Caracalas; la cinquième le Colisée et le Forum romain; la sixième le Forum romain et les thermes de Caracalas; la septième le musée du Vatican et le forum romain.
Ces agences peuvent-elles organiser les visites sur les trois premiers jours de la semaine?

Exercice 7

Utilisez l'algorithme de coloration de Welsh et Powell pour colorer les graphes des exercices 2 et 5.

Exercice 8

Exprimez la résolution d'un Sudoku classique en termes de coloration de graphe. Décrivez le graphe (nombre de sommets, nombre d'arêtes, etc.). Combien faut-il de couleurs?

Didier Müller, 13.2.03