Chapitre 7

PROBLEMES DE COLORATION
7.1 Quelques problèmes
Regardons quelques situations plus ou moins courantes :

Exemple 7.1.1 Un groupe de 8 personnes doit participer à deux réunions. À la première

réunion, ils sont tous assis autour d’une table ronde. Comme l’entente est totale, pour la se-
conde réunion, chacun des participants, non seulement ne veut pas se retrouver à côté de l’un
ou l’autre de ses voisins, mais ne veut pas non plus qu’ils soient assis à la même table.
1. Combien de tables au minimum seront alors nécessaires ? Combien de personnes au maxi-
mum pourront s’asseoir à une même table ?
2. On suppose maintenant qu’il y a 9 participants et que l’entente est tout aussi cordiale.
Que se passera-t-il alors ?

Exemple 7.1.2 Pendant un festival, on veut organiser des tournois de scrable (S), échecs (E),
go (G), dames (D), tarot (T ) et master-mind (M ). Plusieurs personnes se sont inscrites à la
fois pour les tournois E, S, G, d’autres personnes pour les tournois G, D, M , et en…n d’autres
personnes pour les tournois M , T , S. Il est entendu qu’une participation simultanée à plusieurs
tournois est impossible et que les organisateurs veulent satisfaire tout le monde.
1. Quel est le nombre maximum de tournois qui pourraient se dérouler en même temps ?
2. En sachant que chaque tournoi doit durer au maximum 3 heures, proposer un horaire des
tournois nécessitant une durée minimale et respectant bien sûr les choix des participants.

Exemple 7.1.3 Voici la carte du pays d’Ovalie avec ses 5 régions A, B, C, D et E. On veut
colorier cette carte de telle manière que deux régions frontalières aient des couleurs di¤érentes.
Combien de couleurs au minimum faudra-t-il prévoir ?

Exemple 7.1.4 On se donne n points dans l’espace. Certains sont reliés par des segments,
d’autres non, et chacun des points est relié au maximum à 3 autres points. Prouver qu’il existe
au moins n4 points tels que 2 d’entre eux ne soient pas reliés.

ENS Yaoundé, MATH4 Notes de cours MAT4321 @HugueTchantcho 2021-2022

7.2 Nombre chromatique 92

7.2 Nombre chromatique

A partir des exemples précédents et de leurs discussions, on peut donner quelques dé…ni-
tions :

Dé…nition 7.2.1 Une coloration d’un graphe consiste en l’attribution de couleurs aux som-
mets, de telle manière que deux sommets voisins n’aient pas la même couleur.
Une coloration du graphe avec k couleurs sera appelé k-coloration. On dit alors que le graphe
est k colorable.

Remarque 7.2.1 :

On peut se demander ce que sont ces mystérieuses “couleurs”. Il s’agit simplement d’un
moyen de donner un contenu intuitif à une notion utile dans des contextes très variés. D’un
point de vue formel, l’ensemble des couleurs est un ensemble …ni C quelconque, et un coloriage
est tout simplement une application de l’ensemble X des sommets du graphe dans l’ensemble
C, telle que deux sommets adjacents aient toujours des images distinctes.
Dans les exemples, cet ensemble …ni peut être un ensemble de tranches horaires dans les-
quelles on doit faire tenir diverses occupations de façon compatible, de cages de zoo dans
lesquelles il ne faut pas mettre des animaux qui vont s’attaquer, de salles de classes dans les-
quelles on veut organiser des options, etc. . .. Une grande partie de la di¢ culté tient ici dans
le travail de modélisation, pour faire apparaître la question comme un problème de coloriage.
En particulier, la contruction du graphe n’est pas toujours évidente : pour les problèmes de
coloriage de carte, comme on l’a vu dans l’exercice sur la carte d’Ovalie, c’est le graphe dual
du graphe représenté qu’il faut considérer.
Dans les problèmes de compatibilité, ce ne sont pas les sommets compatibles qu’il faut relier
sur le graphe, comme on a spontanément tendance à le faire, mais les sommets incompatibles.
Il n’est pas dans l’esprit de ce cours d’insister sur le côté formel mais il est par contre utile de
comprendre ce qui pourrait, au départ, apparaître comme une pure récréation mathématique
permet de répondre à des questions naturelles et di¢ ciles.
Un graphe d’ordre n peut toujours être en n couleurs. Cependant, on utilise systématique-
ment le nombre minimum de couleurs : on recherche toujours la coloration minimale.

Exemple 7.2.1 Trois couleurs su¢ sent pour colorier le graphe suivant :

Dé…nition 7.2.2 (Nombre chromatique) Le nombre chromatique d’un graphe G est le

nombre minimum de couleurs nécessaires à son coloriage.
On note d’habitude (G) le nombre chromatique d’un graphe G.

Remarque 7.2.2 Si l’on se donne un coloriage d’un graphe, l’ensemble des sommets d’une
couleur donnée est, par dé…nition, un ensemble stable. C’est donc la même chose de se donner un
k-coloriage, ou une partition en k sous-ensembles stables. En particulier, le nombre chromatique
d’un graphe est le nombre minimum de parties d’une telle partition.

ENS Yaoundé, MATH4 Notes de cours MAT4321 @HugueTchantcho 2021-2022

7.2 Nombre chromatique 93

Les résultats suivants (faciles à prouver) donnent le nombre chromatique de certains graphes
particuliers :

Proposition 7.2.1 :
1. Le nombre chromatique du graphe complet Kn est n.
2 si n est pair
2. Soit Cn le cycle de longueur n. on a : (Cn ) = .
2 si n est impair

Les graphes de nombre chromatique 1 sont triviaux, puiqu’ils n’ont pas d’arêtes. Par contre,
les graphes de nombre chromatique 2 sont tout-à-fait intéressants : Les graphes bipartis in-
terviennent naturellement dans beaucoup de problèmes, en particulier tous les problèmes de
mariage (matching) ; il est clair qu’une autre façon de savoir si un graphe est biparti, c’est de
rechercher son nombre chromatique. On peut donc signaler un critère très intéressant et dont
la preuve est immédiate :

Théorème 7.2.1 Un graphe G = (X; A) est biparti si et seulement si il est 2-colorable.

On ne connait pas de caractérisation intéressante des graphes de nombre chromatique 3 ou

plus. De plus la détermination du nombre chromatique d’un graphe quelconque est un problème
NP-Complet.. La plupart du temps il faut se contenter d’un encadrement, autrement dit d’un
minorant et d’un majorant du nombre chromatique. On a intérêt bien sûr à ce que le minorant
soit le plus grand possible et que le majorant soit le plus petit possible. Si par hasard le minorant
et le majorant sont les mêmes, on a gagné puisqu’on a alors le nombre chromatique du graphe.

7.2.1 Minoration du nombre chromatique

Quelques remarques simples permettent de minorer ce nombre chromatique. Soit H un sous-
graphe d’un graphe G. Il est clair qu’un coloriage de G avec (G) couleurs induit un coloriage
de H avec au plus (G) couleurs. Cela veut dire en fait :

Proposition 7.2.2 Si G est un graphe, alors pour tout sous-graphe H de G on a : (H)

(G).

Cette proposition est très utile car elle donne un minorant du nombre chromatique de G ;
si en plus on peut indiquer un coloriage de G avec (H) couleurs, alors on a exactement
(H) = (G).

Proposition 7.2.3 Soit G un graphe, on a ! (G) (G).

Preuve. Puisque, par dé…nition, 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 ! (G).

Proposition 7.2.4 Soit G un graphe d’ordre n, on a : (G) (G) n

Preuve. Considérons une partition de G en ensembles stables qui réalise le nombre chromatique.
On a donc une partition de G en (G) sous-ensembles, qui sont tous, par dé…nition de (G),
de cardinal au plus (G) ; donc le cardinal de la réunion de ces ensembles est majoré par
(G) (G), d’où l’inégalité (G) (G) n.

ENS Yaoundé, MATH4 Notes de cours MAT4321 @HugueTchantcho 2021-2022

7.2 Nombre chromatique 94

7.2.2 Majoration du nombre chromatique

Il est plus di¢ cile de prouver des majorations générales du nombre chromatique. Si on
arrive à construire un coloriage d’un graphe G avec un nombre m de couleurs, on a forcément
(G) m. En particulier, le nombre chromatique d’un graphe G est inférieur ou égal au
nombre de sommets de G, en donnant à chaque sommet une couleur di¤érente, mais c’est là
une majoration triviale. Une majoration plus …ne est donnée par :

Proposition 7.2.5 Soit un graphe G = (X; A). Alors (G) G + 1.

Preuve. :
Soit n l’ordre de G. Il existe des parties de X qu’on peut colorier avec au plus G + 1
couleurs (il su¢ t de prendre une partie à un élément). Soit alors Y une telle partie de cardinal
maximum. Supposons que Y soit strictement inclus dans X. Il existerait alors un sommet x
de G n’appartenant pas à Y . Or x a au plus G voisins dans Y , par conséquent parmi les
G + 1 couleurs utilisées pour le coloriage de Y , il existe au moins une couleur non utilisée pour
les voisins de x dans Y . En attribuant cette couleur à x, on obtient un coloriage de Y [ fxg
avec toujours au plus G + 1 couleurs, et comme le cardinal de Y [ fxg est strictement plus
grand que celui de Y , on obtient une contradiction avec la dé…nition de Y . Par conséquent on
a Y = X, ce qui veut dire qu’on peut colorier les sommets de G avec au plus G + 1 couleurs,
et donc (G) G + 1.
Le résultat suivant donne non seulement une majoration du nombre chromatique d’un
graphe mais aussi un lien assez simple avec le nombre chromatique de son complémentaire.

Théorème 7.2.2 Pour un graphe G d’ordre n et son complémentaire G, on a : (G)+ G

n + 1.

Preuve. (Exercice)

Proposition 7.2.6 Si G est un graphe d’ordre n, on a : (G) + (G) n+1

Preuve. : Soit Y un sous-ensemble stable de taille maximale. Soit H le graphe engendré par le
complémentaire de Y (H est le sous-graphe de G dont les sommets sont les sommets de G qui
ne sont pas dans Y , et dont les arêtes sont les arêtes de G dont aucune extrémité n’est dans
Y ). On voit facilement que (G) (H) + 1 : à toute coloration de H, on peut associer une
coloration de G avec exactement une couleur de plus en colorant tous les sommets de Y avec
la nouvelle couleur. Par ailleurs, il est clair que (H) est majoré par le nombre n (G) de
sommets de H. On a donc montré que (G) 1 (H) n (G), d’où l’inégalité cherchée.
Le résultat précédent peut permettre des majorations de (G) en trouvant des sous-ensembles
stables de taille maximale. On remarquera que, dès que le graphe n’est pas de petite taille, il
n’est pas du tout évident de trouver un ensemble stable de taille maximale ; en particulier, ce
n’est pas parce qu’un ensemble stable est maximal qu’il est de taille maximale ! La stratégie élé-
mentaire qui consiste à essayer d’augmenter un ensemble stable ne su¢ t donc pas à déterminer
le nombre de stabilité.
Il est clair que, si l’on dispose d’un coloriage, on a une majoration du nombre chromatique,
ce qui montre l’utilité d’avoir une stratégie pour colorier un graphe, stratégie qu’on appellera
algorithme de coloriage. En fait la coloration de graphe quand l’ordre est petit est assez aisée,
mais le problème se complique dès lors que le nombre de sommets augmente. Aussi, pour colorer

ENS Yaoundé, MATH4 Notes de cours MAT4321 @HugueTchantcho 2021-2022

7.2 Nombre chromatique 95

un graphe, des algorithmes ont été développés. L’algorithme que nous avons choisi de présenter
(il en existe d’autres) 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), il
permet juste d’avoir une assez bonne majoration du nombre chromatique.

7.2.3 L’algorithme de coloriage de Welch et Powell

On classe d’abord les sommets du graphe dans l’ordre décroissant de leur degré. On obtient
ainsi une liste x1 ; :::; xn de sommets telle que d(x1 ) ::: d(xn ).
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..
On reprend la démarche en attribuant à chaque fois une nouvelle couleur d’usage au
premier sommet de la liste non encore colorié. On s’arrête dès que tous les sommets ont été
coloriés.

Remarque 7.2.3 C’est un bon algorithme, mais précisons quand même que le nombre de cou-
leurs utilisé par cet algorithme n’est pas forcément le nombre chromatique du graphe.

L’exemple qui suit illustre cela. De plus, on remarquera qu’une partie de l’algorithme n’est
pas entièrement déterminée : en e¤et, s’il y a plusieurs sommets de même degré, l’ordre dans
lequel on les range est arbitraire, donc deux personnes appliquant cet algorithme au même
graphe n’obtiendront pas forcément le même coloriage.

Exemple 7.2.2 Considérons le graphe G dessiné ci-dessous. Ce graphe n’est pas un graphe
quelconque, c’est un graphe de De Bruijn non orienté. Plus précisement c’est le graphe de De
Bruijn U B(2; 3). Ses sommets sont les éléments de Z=8Z, et i et j sont adjacents si i 2j ou
j 2i sont dans f0; 1g.

Appliquons l’algorithme décrit ci-dessus : 1; 3; 6; 4; 2; 5; 0; 7 est une liste des sommets classés
dans l’ordre décroissant de leurs degrés. D’après l’algorithme, à la première étape on attribue
une couleur c1 aux sommets 1 et 6. À la deuxième étape, on attribue une couleur c2 aux sommets
3 et 4. À la troisième étape, on attribue une couleur c3 aux sommets 2, 0 et 7. En…n à la dernière
étape on attribue une couleur c4 au sommet 5. On obtient un coloriage de G avec 4 couleurs,
mais en fait le nombre chromatique de G est 3. En e¤et deux couleurs ne su¢ sent pas car G
admet des triangles comme sous-graphes, par contre, en prenant du bleu pour les sommets 0,

ENS Yaoundé, MATH4 Notes de cours MAT4321 @HugueTchantcho 2021-2022

7.3 Graphe critique 96

2 et 3, du rouge pour les sommets 4, 5 et 7 et du jaune pour les sommets 1 et 6, on obtient un

3-coloriage et donc on a bien (G) = 3. La morale de tout cela est que pour un petit nombre
de sommets, il faut chercher directement le nombre chromatique plutôt que d’utiliser tel ou tel
algorithme.

Remarque 7.2.4 Le nom U B(2; 3) veut dire : graphe de De Bruijn non orienté des mots de
longueur 3 sur un alphabet à 2 lettres ; on dé…nirait de même le graphe U B(d; n) des mots de
longueur n sur un alphabet à d lettres. On verra ci-dessous dans les exercices le graphe U B(2; 4).
La complexité de ces graphes augmente très vite avec d et n !

7.3 Graphe critique

Dé…nition 7.3.1 Un graphe G est critique si pour tout sous-graphe propre H de G, (H) <
(G). Lorsque (G) = k on dit alors que G est k-critique.

Remarque 7.3.1 Dans un graphe critique, la suppression d’une arête et d’un sommet réduit le
nombre chromatique ; (G a) < (G) et (G x) < (G) 8a 2 A et 8x 2 X. Tout graphe
complet Kn est n critique, car dans Kn a avec a = xy, les sommets x et y peuvent avoir la
même couleur.

Exemple 7.3.1 Le graphe complet K2 est le seul graphe 2-critique. Les graphes 3-critiques sont
exactement les cycles C2n+1 de longueur impaire, car un graphe 3-critique n’est pas biparti, et
par conséquent peut avoir un cycle de longueur impaire.

Le théorème suivant fourni une condition nécessaire pour qu’un graphe soit critique.

Théorème 7.3.1 Soit un graphe G = (X; A) k-critique avec k 2. Alors G est connexe et
G k 1.

Preuve. Notons d’abord que pour tout graphe G ayant m composantes connexes G1 ; G2 ; : : : ; Gm ,
on a (G) = max f (Gi ) ; i 2 f1; : : : ; mgg. la connexité de G est donc assurée. Supposons alors
G k-critique mais G k 2. Soit x 2 X tel que G = d (x) Comme G est critique, G x
est (k 1)-colorable. Notons fv1 ; v2 ; : : : ; vk 1 g une (k 1)-coloration de G x. Par dé…nition,
x est adjacent à G < k 1 sommets et par conséquent est non adjacent à au moins un som-
met de G de couleur vj , j 2 f1; : : : ; k 1g. Mais alors si on recolorie x par vj , alors G est
(k 1)-colorable : ce qui est absurde. Donc G > k 2.
L’item 3 du théorème suivant est dû à Szekeres et Wilf (1968)

Théorème 7.3.2 Soit un graphe G = (X; A) de nombre chromatique (G) = k.

1. G a un sous-graphe k-critique.
2. G a au moins k sommets de degré supérieur ou égal à k 1.
3. k 1 + max H.
H G

ENS Yaoundé, MATH4 Notes de cours MAT4321 @HugueTchantcho 2021-2022

7.3 Graphe critique 97

Preuve. ;
Pour 1) remarquons simplement qu’un sous-graphe k-critique de G est obtenu par suppres-
sion de sommets et d’arêtes tant que le nombre chromatique ne change pas.
Pour 2) soit H un sous-graphe k-critique de G. D’après le théorème précédent dH (x) k 1
pour tout sommet x de H. Et par conséquent dG (x) k 1 pour tout sommet x de H. Le
résultat escompté suit immédiatement car un graphe k-critique possède au moins k sommets.
Pour 3) soit H un sous-graphe k-critique de G. D’après le théorème précédent k 1 H,
d’où le résultat.
Proposition 7.3.1 Soit x un point d’articulation d’un graphe connexe G et soit Hi , i 2
f1; : : : ; mg les composantes connexes de G x. Notons Gi = G [Hi [ fxg]. Alors (G) =
max f (Gi ) ; i 2 f1; : : : ; mgg. En particulier, un graphe critique n’a pas de point d’articulation.
Preuve. Supposons chaque Gi k-colorable par i . Alors i génère une k-coloration de G par
permutation de couleurs.
Dans la suite nous nous intéressons à la caractérisation par Brooks (1941) des graphes
dont le nombre chromatique véri…e l’égalité dans la proposition 7.2.5. Mais nous aurons besoin
du résultat suivant qui caractérise les graphes 2-connexes.
Proposition 7.3.2 Soit G = (X; A) un graphe 2-connexe. Alors les a¢ rmations suivantes
sont équivalentes :
(i) G est un graphe complet ou un cycle.
(ii) Pour tout x; y 2 X, si xy 2= A, alors fx; yg est une articulationn de G.
(iii) Pour tout x; y 2 X, si dG (x; y) = 2, alors fx; yg est une articulationn de G.
Preuve. :
Il est clair que (i) ) (ii), et que (ii) ) (iii). Montrons alors que (iii) ) (i).
Supposons (iii) et montrons que soit G est complet, soit dG (x) = 2 pour tout x 2 X.
Nontons déjà que dG (x) 2 car G est 2-connexe. Soit z un sommet de degré maximal,
dG (z) = G .
Si l’ensemble VG (z) des voisin de z engendre un sous-graphe complet alors G est complet.
En e¤et, sinon comme G est connexe, il existerait un sommet y 2 = VG (z) [ fzg tel que y soit
adjacent à un sommet x 2 VG (z). Mais alors dG (x) > dG (z), ce qui contredit le choix de z.
Supposons alors qu’il existe deux sommets distincts x; y 2 VG (y) tels que xy 2 = A. Ceci
signi…e que dG (x; y) = 2 (la plus petite chaîne (x; z; y)) et grâce à (iii), fx; yg est une articula-
tionn de G. Par conséquent il existe une partition fZ; fx; yg ; Y g de X telle que z 2 Z et toute
chaîne d’extrémité un sommet de Z et un sommet de Y passe par x ou y.
Nous avons Z = fzg et par conséquent G = 2. Supposons le contraire, c’est-à-dire que
jZj > 1. Comme z n’est pas un point d’articulation (car G n’en a pas), il existe un sommet
u 2 Z tel que u 6= z et xu 2 A ou yu 2 A. Supposons xu 2 A.
Comme y n’est pas un point d’articulation, il existe v 2 Y tel que xv 2 A. Ainsi dG (u; v) = 2,
et par (iii), fu; vg est une articulation de G. Par conséquent il existe une partition fZ1 ; fu; vg ; Y1 g
de X telle que toute chaîne d’extrémité un sommet de Z1 et un sommet de Y1 passe par u ou
v. Supposons que z 2 Z1 , et par conséquent aussi que x; y 2 Z1 (puisque xz; yz sont des arêtes
de G fu; vg).
Il existe donc un vecteur w 2 Y1 : nontons que Y1 Z [ Y . Si w 2 Z (ou w 2 Y ,
respectivement), alors toute chaîne d’extrêmité w et x passe par u (ou v, respectivement), et u
(ou v, respectivement), sera un point d’articulation de G. Ce qui est contradictoire.

ENS Yaoundé, MATH4 Notes de cours MAT4321 @HugueTchantcho 2021-2022

7.4 Polynôme chromatique 98

Théorème 7.3.3 (Brooks 1941) Soit G = (X; A) un graphe connexe. Alors (G) = G +1
si et seulement si G est un cycle de longueur impaire ou un graphe complet.

Preuve. :
() Le résultat est immédiat puisque (C2n+1 ) = 3, GC2n+1 = 2 et (Kn ) = n, GKn =
n 1.
)) Posons k = (G). Nous allons supposer que G est k-critique. En e¤et supposons la
proposition vraie pour les graphes k-critiques. Supposons que k = (G) = G + 1, et soit H un
sous-graphe propre k-critique de G. Comme (H) = k = G + 1 > H , on a (H) = H + 1,
et par conséqent H est complet ou un cycle de longueur impaire. De plus G est connexe, et
donc il existe une arête xy 2 A telle que x est un sommet de H et y n’est pas un sommet de
H. Mais dans ce cas dG (x) > dH (x) et G > H puisque H = Kn ou H = Cn .
Supposons alors G k-critique avec k 2. De par la proposition7.3.1 G est 2-connexe. Si
G est un cycle de longueur paire, alors k = 2 = G . Supposons maintenant que G n’est ni
complet ni un cycle. Montrons que (G) G.
De part la proposition7.3.2, il existe x1 ; x2 2 X tels que dG (x1 ; x2 ) = 2, disons x1 x; xx2 2 A
avec x1 x2 2 = A, tels que H = G fx1 ; x2 g soit connexe. Considérons l’ordre des sommets suivant
x3 ; x4 ; : : : ; xn tel que vn = x et pour tout i 3, dH (xi ; x) dH (xi+1 ; x).
Il en découle que pour tout i 2 f1; : : : ; n 1g, il existera au moins un j > i tel que xi xj 2 A
(possible que xj = x). En particulier, pour tout i 2 f1; : : : ; n 1g, jVG (xi ) \ fx1 ; x2 ; : : : ; xi 1 gj <
dG (xi ) G.
On dé…nit alors la coloration des sommets pris dans l’ordre suivant x1 ; x2 ; : : : ; xn de la ma-
nière suivante : (x1 ) = 1 = (x2 ) et (xi ) = min fr j r 6= (xj ) pour tout xj 2 VG (xi ) avec j < ig.
est une coloration de G. De par l’inégalité jVG (xi ) \ fx1 ; x2 ; : : : ; xi 1 gj G , il ressort
que (xi ) G pour tout i 2 f1; : : : ; n 1g. De même x = xn a deux voisins x1 et x2 , ayant
la même couleur 1, et comme xn a au plus G voisins, il y a donc une couleur disponible pour
xn et par conséquent (xn ) G . Ce qui prouve bien que G est G -colorable, il s’en suit
(G) G .

Exemple 7.3.2 Supposons donné n objets X = fx1 ; x2 ; : : : ; xn g, certains ne sont pas com-
patibles avec d’autres ( exemple par réaction chimique entre eux, ou pire, des des députés qui
pourront se bagarer lors d’une session parlementaire). Dans les problèmes de stockage, on ai-
merait trouver une partition de l’ensemble X ayant un nombre minimal de classes possible de
telle sorte qu’aucune classe ne contienne deux éléments incompatibles. En théorie de graphe
ceci se résoud par la considération d’un graphe G = (X; A), où xi xj 2 A juste dans le cas où
xi et xj sont incompatibles, et on aimerait donc colorier G avec un nombre minimal de couleur
possible. Ce problème requiert la détermination de (G).

7.4 Polynôme chromatique

Jusqu’à présent, nous nous sommes intéressés à la possibilité de colorier ou non un graphe
donné à l’aide de k couleurs. La question suivante serait de déterminer le nombre de façons
distinctes de réaliser un tel coloriage.
Soit G = (X; A) un graphe non orienté ayant n sommets. On dénote par mk;G , le nombre
de coloriages propres distincts de G utilisant exactement k couleurs et par z k , le polynôme
en z 2 C de degré k, z k = z (z 1) (z k + 1) :

ENS Yaoundé, MATH4 Notes de cours MAT4321 @HugueTchantcho 2021-2022

7.4 Polynôme chromatique 99

Dé…nition 7.4.1 Le polynôme chromatique d’un graphe G = (X; A) est donné par
X
n
mk;G
G (z) = zk
k=1
k!

Il s’agit d’un polynôme de degré n en la variable z.

m k;G
Remarque 7.4.1 La quantité k! est le nombre de partitions de X en k sous-ensembles (dis-
joints et non vides) donnant lieu à tous les coloriages propres possibles de G utilisant exactement
k couleurs. En fait, cette quantité équivaut au nombre de partitions de X en k sous-ensembles
(disjoints et non vides) de sommets indépendants.

Exemple 7.4.1 Soit le graphe ci-dessous.

Considérons les partitions de X en k sous-ensembles (disjoints et non vides) donnant lieu à

tous les coloriages propres possibles de G utilisant exactement k couleurs, k 2 f1; 2; 3; 4g

Pour k = 2, on a la partition X = fx1 ; x4 g [ fx2 ; x3 g et les coloriages 1 : x1 ; x4 7!

m2;G
1; x2 ; x3 7! 2 et 2 : x1 ; x4 7! 2; x2 ; x3 7! 1. Ainsi, m2;G = 2 et 2! = 1 correspond bien à la
seule partition convenable de X .
Pour k = 3, on a deux partitions possibles de X en fx1 g[fx4 g[fx2 ; x3 g ou bien fx2 g[fx3 g[
fx1 ; x4 g. Chaque partition donne lieu à 3! coloriages propres distincts de G. Ainsi, m3;G = 12
m
et 3!3;G = 2.
m
Pour k = 4, il y a une seule partition de X en quatre singletons donc 4!4;G = 1.
m
Pour k = 1, on a 1!1;G = 0.
Par conséquent, le polynôme chromatique du graphe est donné par
m1;G m2;G m3;G m4;G
z+ z (z 1) + z (z 1) (z 2) + z (z 1) (z 2) (z 3)
1! 2! 3! 4!
ou encore

G (z) = z (z 1) + 2z (z 1) (z 2) + z (z 1) (z 2) (z 3)
= z 4 4z 3 + 6z 2 3z

ENS Yaoundé, MATH4 Notes de cours MAT4321 @HugueTchantcho 2021-2022

7.4 Polynôme chromatique 100

Exemple 7.4.2 Pour le graphe complet Kn , les seuls ensembles de sommets indépendants sont
mk;G
les singletons. Ainsi, pour tout k < n, k! = 0 et donc Kn (z) = z n .

Voici quelques remarques immédiates.

Remarque 7.4.2 :
1. Si G possède n sommets, alors mn;G = n! car on assigne une couleur par sommet. On en
déduit que le polynôme chromatique est monique.
2. Si G n’est pas connexe mais possède deux composantes connexes G1 et G2 , alors G (z) =
G1 (z) G2 (z). Cela résulte du fait que les sommets de G1 peuvent être colorés indépen-
damment de ceux de G2 .
D’une manière générale si G a pour composantes connexes G1 ; G2 ; : : : ; Gm , alors

G (z) = G1 (z) G2 (z) Gm (z)

3. Il est clair que G (z) = 0 pour tout graphe G.

4. Il est impossible de colorier un graphe non vide avec aucune couleur.

Proposition 7.4.1 Soit k 2 N. Le nombre G (k) est le nombre de coloriages propres de G

utilisant au plus k couleurs.

Preuve. :
Tout d’abord, il est inutile de considérer dans l’expression de (k), les termes d’exposant
G
P
k
mi;G i
supérieur à k. En e¤et, si i > k, alors z i évalué en k est nul. Ainsi, on a G (z) = i!
z.
i=1
m
Ensuite, pour tout i k, on dispose de i!i;G partitions de X en i sous-ensembles de sommets
indépendants. Considérons ces partitions et autorisons-nous cette fois à choisir i couleurs parmi
k, pour chaque partition X1 [ [ Xi de X , à X1 , on peut assigner k couleurs, pour X2 , on
m
a k 1 choix possibles, . . . et pour Xi , on a k i + 1 choix possibles. Ainsi, chacune des i!i;G
partitions de X en i sous-ensembles donnent lieu à k i coloriages utilisant exactement i des k
couleurs disponibles. La conclusion en découle.

Exemple 7.4.3 Avec le graphe de l’exemple précédent, si on calcule G (4), on trouve G (4) =
84 et donc, il y est possible de colorier proprement G avec au plus 4 couleurs de 84 façons
distinctes.En continuant l’exemple précédent, le nombre de coloriages de ce graphe utilisant au
plus 3 couleurs vaut
m1;G m2;G m3;G
G (3) = z+ z (z 1) + z (z 1) (z 2) = 0 + 6 + 12 = 18
1! 2! 3!
Ces coloriages sont donnés par

x1 x2 x3 x4 x1 x2 x3 x4 x1 x2 x3 x4
1 2 1 2 1 2 1 3 2 1 3 1
2 1 2 1 1 3 1 2 3 1 2 1
1 3 1 3 2 1 2 3 1 2 3 2
3 1 3 1 2 3 2 1 3 2 1 2
2 3 2 3 3 1 3 2 1 3 2 3
3 2 3 2 3 2 3 1 2 3 1 3

ENS Yaoundé, MATH4 Notes de cours MAT4321 @HugueTchantcho 2021-2022

7.4 Polynôme chromatique 101

De la proposition précédente on déduit le résultat suivant :

Proposition 7.4.2 Le nombre chromatique de G est le plus petit entier k tel que G (k) 6= 0.

Ainsi, la détermination du nombre chromatique d’un graphe à n sommets peut se ramener

à l’estimation des zéros d’un polynôme de degré n.
Par exemple, avec le graphe précédent, on a G (1) = 0 et G (2) 6= 0.
Il est parfois assez di¢ cile de déterminer le polynôme chromatique d’un graphe. Les résultats
qui suivent donnent une technique permettant d’obtenir le polynôme chromatique d’un graphe.

Dé…nition 7.4.2 (Contraction de graphe) Soient G = (X; A) un multi-graphe (non orienté) et

a 2 A. La Contraction du graphe G suivant l’arête a est le graphe G a obtenu par suppression
de l’arête a et en identi…ant les extrémités de celle-ci.

Par exemple voici un graphe G et le graphe G a

Remarque 7.4.3 Si G est connexe et si a est une arête qui n’est pas une boucle, alors G a
est connexe aussi et contient une arête et un sommet de moins que G.

Proposition 7.4.3 Si a est une arête de G (qui n’est pas une boucle), alors le polynôme chro-
matique satisfait la relation G (z) = G a (z) G a (z)

Preuve. Si on considère tous les coloriages propres de G a avec exactement k couleurs. Il y

en a de deux types : ceux pour lesquels on assigne aux extrémités de a deux couleurs distinctes
(resp. une même couleur). Ceux du premier type sont en bijection avec les coloriages propres de
G utilisant k couleurs. Pour conclure, on remarque que ceux du second type sont en bijection
avec les coloriages propres de G a utilisant k couleurs.
Le résultat suivant est une conséquence de la proposition précédente.

Proposition 7.4.4 Le polynôme chromatique d’un arbre G à n sommets vaut G (z) = z (z 1)n 1 .

Preuve. On procède par récurrence sur n. Le cas n = 1 est immédiat. Supposons le résultat
acquis pour n 1 et véri…ons-le pour n + 1. Si un arbre possède n + 1 sommets, il a au moins
un sommet de degré 1 et soit a, l’arête incidente à ce sommet. Ainsi, G a possède deux
composantes : un sommet isolé dont le polynôme chromatique vaut z et un arbre à n sommets
(qui n’est autre que la contraction G a) de polynôme chromatique z (z 1)n 1 (par hypothèse
de récurrence). On en conclut que G a (z) = z G a (z). Et par la proposition précédente,
G (z) = G a (z) G a (z) = (z 1) G a (z) = z (z 1)n .

Exemple 7.4.4 Reprenons le graphe G d’ordre 4 précédent et déterminons son polynôme chro-
matique.

ENS Yaoundé, MATH4 Notes de cours MAT4321 @HugueTchantcho 2021-2022

7.5 Coloration des graphes planaires 102

G G a G a

G a G fa; bg (G a) b

On a alors

G a (z) = G fa;bg (z) (G a) b (z)

3 2
= z (z 1) z (z 1)
2
= z (z 1) (z 2)

d’où

G (z) = G a (z) G a (z)

2
= z (z 1) (z 2) z (z 1) (z 2)
= z 4 5z 3 + 8z 2 4z

La proposition 7.4.3 permet de réduire la détermination du polynôme chromatique du graphe

à partir de ses contractions succéssives jusqu’à obtenir un graphe dont le polynôme chromatique
est connu (arbre et parfois graphe complet).

7.5 Coloration des graphes planaires

Le problème le plus célèbre de l’histoire de la théorie des graphes est le nombre chromatique
des graphes du planaires. Connu depuis plus de 120 années sous le nom de "Conjecture de
quatre couleurs" il a été résolu par APPEL ET HAKEN en 1976 : si G est un graphe planaire
alors (G) 4. La Conjecture de 4 couleurs a eu une in‡uence profonde en théorie de graphe
pendant les 150 dernières années. La preuve du Théorème de 4 couleurs est di¢ cile, et exige
pour l’instant l’assistance d’un ordinateur.

Théorème 7.5.1 Toute carte de géographie peut être coloriée avec 4 couleurs

Il faut un peu préciser : on suppose que la carte est dessinée sur un plan (ou une sphére, cela
revient au même), que les régions sont raisonnables (disons, des polygones connexes), et que
deux régions ayant une frontière commune sont de couleurs distinctes. On n’exige pas que deux
régions qui ont seulement un coin en commun aient des couleurs distinctes, sinon on trouverait
immédiatement un contre-exemple en divisant un disque en secteurs se touchant au centre.

ENS Yaoundé, MATH4 Notes de cours MAT4321 @HugueTchantcho 2021-2022

7.5 Coloration des graphes planaires 103

Pour démarrer la preuve, on remplace la carte par son graphe dual (dont les sommets sont
les régions de la carte, deux sommets étant adjacents si les régions correspondantes ont une
frontière commune). Ce graphe est par contruction un graphe planaire, et on est donc amené à
montrer que le nombre chromatique d’un graphe planaire est au plus de 4.
Ceci a été fait en 1976 par Appel et Haken, dans une démonstration très longue qui consiste
à se ramener à un nombre …ni, mais grand, de con…gurations, et à prouver que pour chacune des
ces con…gurations, 4 couleurs su¢ sent. La …n de la preuve a été faite par ordinateur, soulevant
une controverse sur la validité d’une preuve qui n’est pas entièrement véri…able à la main,
mais dépend du fonctionnement d’un programme ; par contre, il est facile de démontrer que 5
couleurs su¢ sent.
On peut généraliser ce problème aux cartes dessinées sur un tore, ou plus généralement
sur un bretzel à g trous. Curieusement, c’est plus facile que sur la sphère,pet l’on sait depuis
longtemps que le nombre de couleurs nécessaires est la partie entière de 7+ 1+48g
2
.

Proposition 7.5.1 Si G est un graphe planaire alors (G) 6.

Preuve. Elle se fait par récurrence sur l’ordre n de G. Il est clair que le résultat est acquit
pour n 6. D’après le théorème de Heawood sur le diamètre d’un graphe, G étant planaire, il
admet un sommet x tel que dG (x) 5. Par hypothèse de récurrence, (G x) 5. Comme
dG (x) 5, il existe une couleur c disponible dpour x dans la 6-coloration de G x et par
conséquent (G) 6.
Le théorème suivant est plus connu sous le nom de théorème des cinq couleurs.

Théorème 7.5.2 (Heawood(1890)) Si G est un graphe planaire alors (G) 5.

Preuve. :
Supposons cette a¢ rmation fausse, et soit G un graphe planaire 6 critique. Rappelons que
pour un graphe k critique H, on a H k 1, et par conséquent, il existe un sommet x tel que
dG (x) = G 5. Par le théorème de Heawood sur le diamètre d’un graphe, on a dG (x) = 5.
Soit une 5 coloration propre de G x. Une telle coloration existe puisque G un graphe
6 critique. Par hypothèse, (G) > 5, et par conséquent pour chaque i 2 f1; 2; 3; 4; 5g, il existe
un voisin xi 2 NG (x) tel que (xi ) = i. Supposon les voisins de x repartis de la manière
suivante sur la …gure :

Considérons le sous graphe G [i; j] de G formé des sommets des couleurs i et j. Les sommets
xi et xj sont dans la même composantes connexe de G [i; j] ( sinon, on permutte les couleurs i
et j dans une composante connexe contenant xj a…n d’obtenir une recoloration de G où xi et
xj auront la même couleur i, et alors on recolore v avec l’autre couleur j.

ENS Yaoundé, MATH4 Notes de cours MAT4321 @HugueTchantcho 2021-2022

7.5 Coloration des graphes planaires 104

Soit pij un chemin d’extrémités xi et xj dans G [i; j], et posons C = (xx1 ) p13 (x3 x). Par
conception géométrique, exactement un des sommet x2 ou x4 est contenu dans la région déter-
miné par le cycle C. Maintenant le chemin p24 rencontre le cycle C à certains sommets de C,
puisque G est planaire. Ce qui est contradictoire puisque les sommets de p24 sont coloriés par
2 et 4, mais C ne contient aucune de ces couleurs.
Le théoème des quatre couleurs suivant est dû à Appel et Haken en 1976.

Théorème 7.5.3 (Heawood(1890)) Si G est un graphe planaire alors (G) 4.

De par le théorème suivant, tout graphe planaire peut se décomposer en deux graphes
bipartis.

Théorème 7.5.4 Soit G = (X; A) un graphe tel que (G) 4. Alors l’ensemble des arêtes
A de G peut se partitionner en deux parties A1 et A2 telles que (X; A1 ) et (X; A2 ) soient des
graphes bipartis.

Preuve. Soit Xi = 1 (i) l’ensemble des sommets de couleur i dans la 4 coloration de G.

On dé…nit Ai comme étant l’ensemble des arêtes de G qui relient les ensembles V1 et V2 ; V1
et V4 ; V3 et V4 . Notons A2 le reste des arêtes, c’est-à-dire reliant les ensembles V1 et V3 ; V2 et
V3 ; V2 et V4 . Il est clair que (X; A1 ) et (X; A2 ) sont des graphes bipartis car chaque Vi est un
stable.

ENS Yaoundé, MATH4 Notes de cours MAT4321 @HugueTchantcho 2021-2022