On considère le graphe ci-dessous. On note Γ son nombre chromatique.
Donner un encadrement du nombre chromatique.
Tableau des degrés des sommets :
| Sommet | A | B | C | D | E | F | G | H | I |
| Degré du sommet | 4 | 3 | 6 | 3 | 4 | 5 | 5 | 3 | 3 |
Le plus haut degré des sommets est 6 par conséquent, .
(A; C; G; D) est un sous-graphe complet d'ordre 4 par conséquent, .
Donc le nombre chromatique Γ est tel que .
Donner une coloration de ce graphe.
Donnons une coloration de ce graphe à l'aide l'algorithme de Welsh et Powell (algorithme glouton)
Étape 1 : On numérote les sommets par ordre de degré décroissant. C-F-G-A-E-B-D-H-I
Étape 2 : En parcourant la liste dans l'ordre , attribuer une couleur d'usage 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.
On attribue la couleur 1 aux sommets C et H.
Étape 3 : Tant qu'il reste des sommets non colorés dans le graphe, revenir à l'étape 2.
On attribue alors la couleur 2 aux sommets F et A, la couleur 3 aux sommets G et E puis la couleur 4 aux sommets B, D et I
En déduire la valeur du nombre chromatique de .
Le nombre chromatique Γ est tel que or il suffit d'utiliser 4 couleurs différentes pour colorier le graphe .
Le nombre chromatique de est .
Les documents présentés ne sont pas libres de droits. Vous pouvez les télécharger et diffuser (en indiquant la provenance) à condition de ne pas en faire un usage commercial.