Chapitre 5
Coloration de graphes
5.1 Introduction et généralités
Une coloration d’un graphe G = (V, E) est une application c : V → S. Une coloration c est propre si pour
toute arête uv ∈ E(G), c(u) 6= c(v). Les éléments de S sont appelés les couleurs. Comme la seule chose de S
qui nous intéresse est sa taille, on considére souvent que S = {1, 2, . . . , k}. Une k-coloration d’un graphe G
(sans boucle) est une coloration propre de G à valeur dans {1, 2, . . . , k}. Un graphe est k-colorable s’il admet
une k-coloration. Le plus petit entier k tel que G soit k-colorable est le nombre chromatique de G, noté χ(G).
Proposition 5.1 Si H est un sous-graphe de G alors χ(H) ≤ χ(G).
Preuve: Si c est une coloration propre de G alors c est clairement une coloration propre de H.
Proposition 5.2 χ(G) = max{χ(C), C composante connexe de G}.
Preuve: D’après la Proposition 5.1, χ(G) ≥ max{χ(C), C composante connexe de G}. Soit C 1 , C2 , . . . , Ck
les composantes connexes de G. Pour 1 ≤ i ≤ k, soit ci une coloration propre de Ci avec les couleurs
1, 2, . . . , χ(Ci ). Considérons c définie par c(v) = ci (v) si v ∈ Ci . Comme il n’ y a pas d’arêtes entre deux
sommets de composantes connexes différentes, c est une coloration propre de G. Ainsi χ(G) ≤ max{χ(C), C
composante connexe de G}.
Dans la suite, nous considérerons très souvent que les graphes sont connexes.
5.2 Bornes inférieures pour χ(G)
La Proposition 5.1 appliquée à la plus grande clique de G, nous donne immédiatement :
Proposition 5.3
χ(G) ≥ ω(G)
La taille maximale d’une clique est une borne inférieure de χ(G). Malheureusement, ce n’est pas un bon
indicateur du nombre chromatique.
Théorème 5.4 Soit k ≥ 2 un entier. Il existe un graphe G tel que ω(G) = 2 et χ(G) = k.
Preuve: Les graphes de Mycielski Mk , k ≥ 2, sont définis de manière inductive comme suit :
Le graphe M2 à deux sommets reliés par une arête. Il vérifie ω(M2 ) = 2 et χ(M2 ) = 2.
Pour k ≥ 2, posons V (Mk ) = {v1 , v2 , . . . , vn }. Le graphe Mk+1 est défini par V (Mk+1 ) = V (Gk ) ∪
{w1 , w2 , . . . , wn , z} et E(Mk+1 ) = E(Gk ) ∪ {wi vj , vi vj ∈ E(Mk )} ∪ {wi z, 1 ≤ i ≤ n}. Voir Figure 5.1.
47
48 CHAPITRE 5. COLORATION DE GRAPHES
v1 w1
v2 w2
v1 w1 v3 w3 z
z v4 w4
v2 w2 v5 w5
G2 G3 G4
Fig. 5.1 – Les graphes M2 , M3 et M4 .
Montrons par récurrence sur k que ω(Mk ) = 2 pour tout k ≥ 2. Le résultat est vrai pour k = 2. Supposons
maintenant que ω(Mk ) = 2. Montrons par l’absurde que ω(Mk+1 ) = 2. Supposons que Mk+1 ait une clique
C3 à trois sommets ou plus. Comme il n’y a pas d’arêtes entre les sommets wi , C3 contient au plus un
des sommets wi . Donc, z n’est pas un sommet de C3 car ses voisins sont les sommets wi . De plus, comme
ω(Mk ) = 2, C3 n’est pas contenu dans Mk . Comme les sommets Wi ne sont pas voisins entre eux, il y au
plus un sommet wi . Ainsi, C3 est formé de deux sommets vi et vj dans Mk et d’un wl . Alors vi vj , vi wl et
vj wl sont des arêtes. Par construction de Mk+1 , vi vl et vj vl sont aussi des arêtes. Les sommets vi , vj et vl
forment alors une clique dans Mk ce qui contredit ω(Mk ) = 2.
Montrons maintenant par récurrence sur k que χ(Mk ) = k pour tout k ≥ 2. Le résultat est vrai pour
k = 2. Supposons maintenant que χ(Mk ) = k.
Soit c une k-coloration de Mk . Posons c(wi ) = c(vi ) pour 1 ≤ i ≤ n et c(z) = k + 1. Il est facile de voir que
c ainsi étendue est une (k + 1)-coloration de Mk+1 . Donc χ(Mk+1 ) ≤ k + 1.
Supposons maintenant qu’il existe une k-coloration f de Mk+1 . Quitte à réindexer les couleurs, on peut
supposer que f (z) = k. Soit c l’application de V (Mk ) dans {1, 2, . . . , k − 1} définie par c(vi ) = f (vi ) si
f (vi ) 6= k et c(vi ) = f (wi ) sinon. (Notons que f (wi ) 6= k pour tout 1 ≤ i ≤ n car wi z est une arête.)
c est alors une (k − 1)-coloration de Mk . En effet, soit vi vj une arête de Mk , alors soit f (vi ) 6= k et
f (vj ) 6= k et c(vi ) = f (vi ) 6= f (vj ) = c(vj ) ou f (vi ) = k et f (vj ) 6= k. Puisque wi vj est une arête,
c(vi ) = f (wi ) 6= f (vj ) = c(vj ). Ainsi χ(Mk ) ≤ k − 1 ce qui est une contradiction.
On a donc bien χ(Mk+1 ) = k + 1.
Il est clair que dans une coloration propre, les sommets de même couleur forment un ensemble indépen-
dant.
Proposition 5.5
|V (G)|
χ(G) ≥
α(G)
Preuve: Soit c une coloration propre de G avec les couleurs 1, 2, . . . , χ(G) et S i = {v ∈ V (G) : c(v) = i}
pour 1 ≤ i ≤ χ(G). Chaque Si est un ensemble indépendant donc |Si | ≤ α(G). On a donc
χ(G) χ(G)
X X
|V (G)| = |Si | ≤ α(G) ≤ χ(G).α(G)
i=1 i=1
Là encore si |Vα(G)
(G)|
est une borne inférieure pour χ(G) mais n’est pas un bon indicateur en général. En
effet, considérons le graphe G composé de n composantes connexes toutes réduites à un sommet sauf une
qui est un graphe Kk ( graphe complet à k éléments). Alors, χ(G) = k et |Vα(G)(G)|
= n+k−1
n est inférieur à 2
si n est suffisamment grand.
5.3. BORNES SUPÉRIEURES POUR χ(G) 49
5.3 Bornes supérieures pour χ(G)
La plupart des bornes que nous allons établir sont obtenues en utilisant un algorithme glouton. On
prend un ordre σ = (v1 < v2 < . . . < vn ) sur les sommets de G. On colore ensuite les sommets de manière
séquentielle avec les entiers naturels de la façon suivante : le sommet vi est coloré avec le plus petit entier
non utilisé par ses voisins déjà colorés (i.e. d’indice plus petit).
Combien de couleurs cet algorithme glouton utilise-t-il ? Si pour tout i le nombre de couleurs déjà attri-
buées aux voisins de vi parmi v1 , v2 , . . . , vi−1 est au plus D alors l’algorithme glouton utilise au plus D + 1
couleurs. Comme un sommet a au plus ∆(G) voisins, on a alors :
Proposition 5.6
χ(G) ≤ ∆(G) + 1
L’algorithme glouton n’utilise pas nécessairement ∆(G) + 1 couleurs. En particulier, il existe des ordres
pour lesquels l’algorithme de coloration séquentielle est optimal, i. e. utilise χ(G) couleurs : soit c une
coloration propre de G avec les couleurs 1, 2, . . . , χ(G), tout ordre σopt = (v1 < v2 < . . . < vn ) tel que
c(vi ) ≤ c(vj ) si i ≤ j convient. Cependant trouver un tel ordre parmi les n! possibles est difficile.
On peut cependant trouver des ordres qui améliorent la borne ∆(G) + 1 ci-dessus.
Définition 5.7 Soit σ = (v1 < v2 < . . . < vn ) un ordre sur les sommets d’un graphe G. On définit g(σ)
comme le maximum sur 1 ≤ i ≤ n du degré du sommet vi dans le sous-graphe induit par {v1 , v2 , . . . , vi }. La
dégénérescence de G, notée δ ∗ (G) est la valeur minimum de g(σ) sur tout les ordres de sommets σ possibles.
Notons que δ ∗ (G) et un ordre σ ∗ associé peuvent être facilement trouvés. Il suffit de prendre un sommet
de plus petit degré dans G, de le mettre à la fin de l’ordre, de l’enlever de G, et de répéter l’opération.
Clairement on a δ ∗ (G) ≤ ∆(G).
L’algorithme glouton suivant σ ∗ , nous donne alors :
Proposition 5.8
χ(G) ≤ δ ∗ (G) + 1
Proposition 5.9 Soit G un graphe connexe. δ ∗ (G) = ∆(G) si et seulement si G est régulier.
Preuve: Supposons que G soit régulier. Alors pour tout ordre σ = (v1 < v2 < . . . < vn ), le degré de vn dans
G est ∆(G) et donc g(σ) = ∆. D’où δ ∗ (G) = ∆(G).
Supposons que G ne soit pas régulier. Soit v un sommet de degré inférieur à ∆. Prenons un parcours en
profondeur (ou en largeur) (vn , vn−1 , . . . , v1 ) de G de racine vn = v. Alors l’ordre σ = (v1 < v2 < . . . < vn )
vérifie g(σ) < ∆. En effet, tout sommet vi , i < n est relié à un sommet vj > vi . Ainsi δ ∗ (G) < ∆(G).
On peut donc se demander pour quels graphes connexes χ(G) = ∆(G) + 1. C’est clairement le cas pour
les graphes complets Kn d’après la Proposition 5.3 car ω(Kn ) = n = ∆(Kn ) + 1. Il est facile de voir que
c’est aussi le cas pour les cycles impairs pour lesquels ∆ = 2 et qui ne sont pas 2-colorables. Le théorème de
Brooks nous affirme que ce sont intrinsèquement les seuls cas.
Théorème 5.10 (Brooks 1941) Soit G un graphe connexe. Si G n’est ni un graphe complet ni un cycle
impair alors χ(G) ≤ ∆(G).
Nous donnerons deux preuves de ce théorème. La première peuve est basée sur l’algorithme glouton. On
étudie tout d’abord le cas des graphes non 2-connexes puis le cas des graphes 2-connexes.
Rappel : un graphe G est 2-connexe, si pour tout couple de sommets u et v, il existe deux chemins
disjoints allant de u en v.
Preuve:
– Si G n’est pas ∆(G)-régulier, on a le résultat par les Proposition 5.9 et 5.8. On peut donc désormais
supposer que G est ∆(G)-régulier. Si ∆(G) = 2 alors G est un cycle pair. Il est donc 2-colorable. On
peut donc supposer que ∆(G) ≥ 3.
50 CHAPITRE 5. COLORATION DE GRAPHES
– Si G n’est pas 2-connexe, alors il existe un sommet v tel que G − v ait k ≥ 2 composantes connexes
C1 , C2 , . . . , Ck . Chaque graphe Gi induit par V (Ci ) ∪ {v} vérifie ∆(Gi ) ≤ ∆(G) et dGi (v) < ∆(G). Les
graphes Gi ne sont pas réguliers. Ainsi par la Proposition 5.9, chaque Gi est ∆(G)-colorable. Prenant
pour chaque Gi une ∆(G)-coloration ci telle que ci (v) = 1, l’union des ci nous donne une ∆-coloration
de G.
– Supposons maintenant que G soit 2-connexe. Comme G n’est pas le graphe complet, d’après l’exer-
cice 2.12, il existe trois sommets u, v et w tels que uv ∈ E(G), vw ∈ E(G), uw ∈ / E(G) et G − {u, w}
soit connexe. Il existe alors un ordre σ = (v1 = u < v2 = w < v3 < . . . < vn = v) de V (G) \ {u, w}
tel que pour i < n, le sommet vi soit adjacent à un vj avec j > i (il suffit d’ordonner les sommets de
V (G)\{u, w}par rapport à leur distance par rapport à v). Colorons alors u et w avec 1. On peut ensuite
colorer les sommets de V (G) \ {u, w} suivant σ avec la première couleur disponible de {1, 2, . . . , ∆(G)}.
En effet, pour i < n, le sommet vi à au plus ∆(G)−1 voisins déjà colorés, ainsi il peut être coloré par une
des couleurs de {1, 2, . . . , ∆(G)}. Pour le sommet v, il a deux voisins colorés par 1, il est donc adjacent
à au plus ∆(G) − 1 autres couleurs et il peut donc être coloré par une couleur de {1, 2, . . . , ∆(G)}.
Nous donnons maintenant une preuve alternative du Théorème de Brooks qui se fait par récurrence sur
le nombre de sommets :
Preuve: Par récurrence sur |V (G)|. Si ∆(G) ≤ 2, alors G est un chemin ou un cycle et le résultat est trivial.
On peut donc supposer que ∆(G) ≥ 3 et que le résultat est vrai pour les graphes ayant moins de sommets.
Supposons que χ(G) > ∆(G) = ∆.
Soit v un sommet de G et H := G−v. Alors χ(H) ≤ ∆ : par hypothèse de récurrence, chaque composante
connexe H 0 de H vérifie χ(H 0 ) ≤ ∆(H 0 ) ≤ ∆ sauf si H 0 est un graphe complet ou un cycle impair dans quel
cas χ(H 0 ) ≤ ∆(H 0 ) + 1 ≤ ∆.
Assertion 1 : Toute ∆-coloration de H utilise toutes les couleurs 1, . . . , ∆ sur les voisins de v ; en particulier
d(v) = ∆.
[[ Sinon on pourrait colorer v avec la couleur de 1, . . . , ∆ non utilisée sur les voisins de v et on aurait une
∆-coloration de G, ce qui contredit χ(G) > ∆. ]]
Étant donnée une ∆-coloration de H, notons par vi le voisin de v coloré i, 1 ≤ i ≤ ∆. Pour tout i 6= j,
soit Hi,j le sous-graphe de H induit par tous les sommets colorés i ou j.
Assertion 2 : Pour tout i 6= j, les sommets vi et vj sont dans la même composante connexe Ci,j de Hi,j .
[[ Sinon on pourrait interchanger les couleurs i et j dans l’une des deux composantes et v i et vj seraient
colorés de manière identique ce qui contredirait l’Assertion 1. ]]
Assertion 3 : Ci,j est toujours un chemin d’extrémités i et j.
[[ Soit P un chemin de vi à vj dans Ci,j . Comme dH (vi ) ≤ ∆ − 1, les voisins de vi sont tous de couleurs
différentes. Sinon on pourrait recolorer vi , ce qui contredirait l’Assertion 1. Ainsi le voisin de vi dans
P est le seul voisin de vi dans Ci,j . De même, le voisin de vj dans P est le seul voisin de vj dans Ci,j .
Donc si Ci,j 6= P , alors P a un sommet interne avec trois voisins dans H colorés identiquement ; soit
u le premier de tels sommets sur P . Au plus ∆ − 2 couleurs sont utilisées par les voisins de u qui peut
donc être recoloré. Alors Q le sous-chemin de P allant de vi au prédécesseur de u est une composante
de Hi,j pour cette nouvelle coloration. Cela contredit l’Assertion 2. ]]
Assertion 4 : Pour des entiers i, j, k distincts, les chemins Ci,j et Ci,k ne se rencontrent qu’en vi .
[[ Si vi 6= u ∈ Ci,j ∩ Ci,k alors u possède deux voisins colorés j et deux voisins colorés k. On peut donc
recolorer u. Pour cette nouvelle coloration i et j sont alors dans deux composantes différentes de H i,j
ce qui contredit l’Assertion 2. ]]
Si G n’est pas le graphe complet, deux voisins de G, disons v1 et v2 , ne sont pas adjacents. Soit u 6= v2 le
voisin de v1 dans C1,2 . Interchangeons les couleurs 1 et 3 dans C1,3 . Seules les premières couleurs de C1,2 et
de C3,2 seront échangés. On obtient alors une nouvelle coloration c0 de H. Afin d’éviter les confusions notons
vi0 , Hi,j
0 0
et Ci,j , les nouveaux vi , Hi,j et Ci,j , pour c0 .
– Comme c0 (u) = c(u) = 2, u appartient à H2,3 0
. De plus u est un voisin de v1 = v30 , donc u appartient à
0
la composante connexe C2,3 .
0
– Comme c(u) = 2, alors u appartient à H1,2 . De plus, les couleurs de C1,2 −v1 sont inchangées, car d’après
5.4. COLORATION DES GRAPHES PLANAIRES 51
l’Assertion 4 C1,2 n’a aucun sommet commun avec C1,3 . Donc C1,2 − v1 fait parti de la composante
0 0
connexe C1,2 . Le sommet u est donc inclus dans C1,2 .
0 0
– Ainsi, nous avons u ⊂ C1,2 ∩ C2,3 ce qui contredit l’Assertion 4.
La borne supérieure ∆ pour χ est loin d’être optimale et elle peut être améliorée pour de nombreuses
classes de graphes. Par exemple, pour les graphes sans triangle (pour lesquels w = 2).
l m
∆(G)+1
Proposition 5.11 Soit G un graphe sans triangle. Alors χ(G) ≤ 3 4 .
l m
Preuve: Posons k = ∆(G)+1 4 . Soit (V1 , V2 , . . . , Vk ) la partition de V (G) en k ensembles telle que le nombre
d’arêtes internes (i.e. avec les deux extrémités dans une même partie) est maximum. Pour tout i, le graphe
Gi induit par Vi est de degré maximum au plus 3. En effet, supposons qu’un sommet x d’une des parties,
disons V1 , ait 4 voisins dans V1 . Alors une autre partie, disons V2 , contient au plus 3 voisins de x, sinon x
aurait au moins 4k ≥ ∆(G) + 1 voisins ce qui est impossible. Ainsi la partition (V1 − x, V2 + x, . . . , Vk ) a
moins d’arêtes internes que (V1 , V2 , . . . , Vk ) ce qui contredit la minimalité de celle-ci.
Ainsi ∆(Gi ) ≤ 3 et Gi ne contient pas de complet à trois éléments car c’est un sous-graphe de G. Donc
par le Théorème de Brooks, χ(Gi ) ≤ 3.
Ainsi en colorant les Gi avec des ensembles de couleurs distinctes, on obtient une 4k-coloration de G.
En fait, on pense que la borne supérieure adéquate est la suivante :
l m
Conjecture 5.12 (Reed 1998) Pour tout graphe G alors χ(G) ≤ ∆(G)+ω(G)+12 .
Dans le cas où w ∈ {∆, ∆ + 1}, cette conjecture est triviale. Le Théorème de Brooks établit cette
conjecture pour ω = ∆ − 1.
Cette conjecture a été prouvé par Johansson pour w = 2 et ∆ suffisamment grand. En fait, Johansson a
c∆(G)
montré qu’il existe une constante c telle que si w(G) = 2 alors χ(G) ≤ log(∆(G)) .
5.4 Coloration des graphes planaires
Définition 5.13 Un graphe planaire est triangulé si toutes ses faces sont des triangles. On appelle triangu-
lation d’un graphe planaire G tout graphe planaire triangulé T tel que V (T ) = V (G) et E(G) ⊂ E(T ).
Proposition 5.14 Tout graphe planaire admet une triangulation.
Preuve: Soit G un graphe planaire. Pour chaque face de G, (x1 , x2 , . . . , xl , x1 ) qui n’est pas un triangle,
rajouter les arêtes x1 xi pour 3 ≤ i ≤ l−1. On vérifie aisément que le graphe ainsi obtenu est une triangulation
de G.
Proposition 5.15 Soit G un graphe planaire.
|E(G)| ≤ 3|V (G)| − 6
Preuve: D’après la Proposition 5.14, il suffit de le montrer pour les graphes planaires triangulés. Soit G un tel
graphe et n (resp. m, f ) son nombre de sommets (resp. arêtes, faces). La formule d’Euler (voir Exercice 5.14)
nous donne n + f = m + 2. Or chaque face contient trois arêtes et chaque arête est dans deux faces. Ainsi
2m = 3f . Remplaçant f par sa valeur dans la formule d’Euler, il vient n + 2m/3 = m + 2 soit 3n − 6 = m.
Corollaire 5.16 Un graphe planaire possède un sommet de degré au plus 5.
52 CHAPITRE 5. COLORATION DE GRAPHES
Preuve: Soit G un graphe planaire. On a {d(v) : v ∈ G} = 2|E(G)| ≤ 6|V (G)| − 12. Le degré minimum
P
de G est au plus égal au degré moyen qui vaut 6|V|V(G)|−12
(G)| < 6. Il y a donc un sommet de degré inférieur à
6.
Corollaire 5.17 Un graphe planaire est 6-colorable.
Preuve: Puisque tout sous-graphe d’un graphe planaire est planaire, tout sous-graphe possède un sommet
de degré au plus 5. La dégénérescence d’un graphe planaire est donc au plus 5. La Proposition 5.8 donne le
résultat.
Théorème 5.18 Tout graphe planaire est 5-colorable.
Preuve: Par récurrence sur le nombre de sommets du graphe G, le résultat étant trivialement vrai si G a un
seul sommet. Par Proposition 5.16, un sommet v est de degré au plus 5 dans G. Par hypothèse de récurrence,
le graphe G − v est 5-colorable. Soit c une 5-coloration de G − v. A partir de c nous allons construire une
5-coloration de G.
Si une des couleurs, disons i, n’est attribuée à aucun voisin de v alors on peut étendre c en posant c(v) = i.
(C’est en particulier le cas si d(v) ≤ 4.)
Nous pouvons donc désormais supposer que v a cinq voisins v1 , v2 , v3 , v4 et v5 dans l’ordre trigonométrique
autour de v. Ceux-ci sont tous colorés d’une couleur différente ; quitte à renommer les couleurs on peut
supposer que c(vi ) = i.
Soit C1,3 la composante de v1 dans le sous-graphe de G induit par les sommets colorés 1 et 3. Si v3 n’est
pas dans C1,3 , alors on peut permuter les couleurs 1 et 3 dans C1,3 et colorer v avec 1. Si v3 ∈ C1,3 , alors il
existe un chemin P de v1 à v3 dans C1 qui avec les arêtes vv1 et vv3 forment un cycle C. Et v2 et v4 sont
séparés par C. Alors la composante C2,4 de v2 dans le sous-graphe de G induit par les sommets colorés 2 et
4 ne contient pas v4 , sinon une arête du chemin de v2 à v4 dans C2,4 couperait une des arêtes de C (voir
Figure 5.2). On peut donc permuter les couleurs 2 et 4 dans C2,4 et colorer v avec 2.
5 4
1 3
Fig. 5.2 – .
Le résultat ci-dessus n’est pas le meilleur possible. En effet, Appel et Haken ont montré la 4-colorabilité
des graphes planaires.
Théorème 5.19 (Appel et Haken 1977) Tout graphe planaire est 4-colorable.
La preuve de ce théorème est très compliquée. Elle consiste en une réduction à un certain nombre de
graphes (plus de 1000) pour lequel le théorème a été prouvé à l’aide de l’ordinateur.
Remarquons que la preuve du Théorème 5.18, ne fonctionne pas pour la 4-coloration. En effet, si nous
sommes dans la configuration de la Figure 5.3, pour toute paire de couleurs i, j, les sommets i et j sont dans
la même composante du sous-graphe induit par les sommets colorés i et j.
5.5. COLORATION DES ARÊTES 53
3 4
1 3
Fig. 5.3 – La configuration problématique : la courbe de i à j représente un chemin de sommets colorés
alternativement i et j.
5.5 Coloration des arêtes
Une arête-coloration d’un graphe G = (V, E) est une application c : E → S telle que pour deux arêtes e
et f adjacentes c(e) 6= c(f ). Une k-arête-coloration d’un graphe G est une coloration dans {1, 2, . . . , k}. Un
graphe est k-arête-colorable s’il admet une k-arête-coloration. Le plus petit entier k tel que G soit k-arête-
colorable est l’indice chromatique de G, noté χ0 (G).
Par définition, χ0 (G) = χ(L(G)), où L(G) est le-line graphe de G.
Il est évident que que tout graphe G vérifie χ0 (G) ≥ ∆(G). Nous allons voir que pour les graphes bipartis,
∆(G) couleurs suffisent.
Théorème 5.20 (König 1916) Si G est un graphe biparti alors χ0 (G) = ∆(G).
Preuve: Par récurrence sur le nombre d’arêtes. Si |E(G)| = 0, le théorème est trivialement vrai. Supposons
maintenant que |E(G)| ≥ 1 et que le résultat est vrai pour les graphes ayant moins d’arêtes. Posons ∆(G) =
∆. Soit xy une arête de G. Par hypothèse de récurrence, G − xy admet une ∆-arête-coloration.
Dans G − xy, les sommets x et y sont chacun incident à au plus ∆ − 1 arêtes. Ainsi il existe c x , cy ∈
{1, 2, . . . , ∆} tels que x (resp. y) ne soit pas adjacent à une arête colorée cx (resp. cy ). Si cx = cy , alors on
peut colorer xy avec cette couleur et on obtient une ∆-arête-coloration de G. Nous pouvons donc supposer
que cx 6= cy et que le sommet x est incident à une arête e colorée cy .
Étendons cette arête en une marche maximale P dont les arêtes sont colorées c y et cx alternativement.
Comme un sommet est adjacent à au plus une arête d’une couleur, P est un chemin. De plus, P ne contient
pas y. Sinon P terminerait en y avec une arête colorée cx et P serait un chemin pair. Mais alors P + xy
formerait un cycle impair, ce qui est impossible d’après la Proposition 1.6. On peut donc recolorer P en
intervertissant les couleurs cx et cy . Par maximalité de P , deux arêtes adjacentes sont toujours de couleurs
différentes. En colorant xy par cy , on obtient alors une ∆-arête-coloration de G.
Ce théorème n’est cependant pas vrai lorsque le graphe n’est pas biparti. Par exemple, pour un cycle
impair, ∆ = 2 mais χ0 = 3.
Théorème 5.21 (Vizing 1964) Pour tout graphe G, ∆(G) ≤ χ0 (G) ≤ ∆(G) + 1.
Preuve: Nous allons prouver la deuxième inégalité par récurrence sur |E(G)|. Pour |E(G)| = 0, le résultat
est trivialement vrai. Supposons maintenant que |E(G)| ≥ 1 et que le résultat est vrai pour tout graphe avec
moins d’arêtes que G. Posons ∆(G) = ∆. Soit xy0 une arête de G. Par hypothèse de récurrence, G − xy0
admet une (∆ + 1)-arête-coloration. Comme y0 est incident au plus ∆ − 1 arêtes dans G − xy0 , il existe
c1 ∈ {1, 2, . . . , ∆ + 1} tel qu’aucune arête incidente à y0 ne soit colorée c1 . Si aucune arête incidente à x n’est
colorée c1 alors, en colorant xy0 par c1 , on obtient une (∆ + 1)-arête-coloration de G. On peut donc supposer
qu’il existe une arête xy1 colorée c1 . Comme y1 est incident au plus ∆ arêtes, il existe c2 ∈ {1, 2, . . . , ∆+1} tel
qu’aucune arête incidente à y1 ne soit colorée c2 . Si aucune arête incidente à x n’est colorée c2 , en recolorant
xy1 par c2 et en colorant xy0 par c1 on obtient une (∆ + 1)-arête-coloration de G. On peut donc supposer
54 CHAPITRE 5. COLORATION DE GRAPHES
qu’il existe une arête xy2 colorée c2 . Et ainsi de suite on construit une suite y1 , y2 , . . . de sommets et une
suite de couleurs c1 , c2 , . . . telles que :
(i) xyi est colorée ci , et
(ii) ci+1 ne colore aucune arête incidente à yi .
Comme le degré de x est fini, il existe un plus petit entier l tel que pour un entier k < l,
(iii) cl+1 = ck .
Maintenant, pour 0 ≤ i ≤ k − 1, recolorons l’ arête xyi avec ci+1 .
Il existe une couleur c0 ∈ {1, 2, . . . , ∆ + 1} qui n’est attribuée à aucune des arêtes incidentes à x. En
particulier, c0 6= ck . Soit P le chemin maximal issu de yk−1 coloré alternativement c0 et ck . Intervertissons
les couleurs c0 et ck sur P + xyk−1 . Si P ne contient pas yk , nous avons une (∆ + 1)-arête-coloration de
G. Si P contient (et termine en) yk , en recolorant l’arête xyi avec ci+1 pour k ≤ i ≤ l, on obtient une
(∆ + 1)-arête-coloration de G.
5.6 Exercices
Exercice 5.1 Trouver le nombre chromatique des graphes suivants :
Exercice 5.2 Soit G un graphe k-régulier biparti. Montrer que pour toute 2-coloration de G, il y a autant
de sommets colorés 1 que de sommets colorés 2.
Exercice 5.3 Montrer qu’un graphe G = (V, E) est 2k -colorable si et seulement si E se partitionne en k
ensembles E1 , . . . , Ek tel que pour tout 1 ≤ i ≤ k, (V, Ei ) soit un graphe biparti.
Exercice 5.4 Si un graphe k-chromatique G admet une coloration pour laquelle toute couleur est assignée
à deux sommets alors G a une k-coloration avec la même propriété.
Exercice 5.5 1) Montrer que si G est biparti alors χ(G) = w(G).
2) Montrer que si G est le complément d’un graphe biparti alors χ(G) = ω(G). On pourra utiliser le
Théorème 3.6.
Exercice 5.6 1) Montrer que χ(G)
p + χ(G) ≤ |V (G)| + 1. On pourra procéder par récurrence sur |V (G)|.
2) Montrer que χ(G) + χ(G) ≥ 2 |V (G)|.
Exercice 5.7 Un graphe d’intervalles à pour ensemble de sommets {I 1 , I2 , . . . , In }, tel que chaque Ij est un
intervalle [ai , bi ] ⊂ IR et deux intervalles Ij et Ik sont reliés par une arête si et seulement s’ils s’intersectent.
Montrer que si G est un graphe d’intervalles alors χ(G) = ω(G).
Exercice 5.8 Montrer que si G est un graphe de comparabilité alors χ(G) = ω(G). Montrer que si G est le
complément d’un graphe de comparabilité alors χ(G) = ω(G). On pourra utiliser le Corollaire 3.14.
Exercice 5.9 Montrer que pour tout k, le graphe de Mycielski Mk est k-critique, i.e. pour tout sommet
v ∈ V (Mk ), χ(G − v) < k.
Exercice 5.10 En 1947, Tutte a construit la suite de graphes G3 , G4 , . . . par récurrence comme suit : G3 est
le cycle à 5 sommets. Supposons que nous ayons construit Gk avec nk sommets. Posons mk = k(nk − 1). Soit
W un ensemble de mk sommets et pour tout sous-ensemble U de W de cardinalité nk , soit GU une copie de
Gk tels que W et les V (GU ) soient tous disjoints. Le graphe Gk+1 et alors obtenu en ajoutant pour chaque
U ⊂ W de cardinalité nk un couplage parfait entre U et V (GU ). On a alors |V (Gk+1 )| = nk+1 = m nk nk +mk .
k
Montrer que pour tout k, Gk est sans triangle (ω(Gk ) = 2) et χ(Gk ) = k.
5.6. EXERCICES 55
Exercice 5.11 Un cographe est un graphe sans sous-graphe isomorphe à P 4 , le chemin à 4 sommets. Montrer
que pour n’importe quel ordre σ sur les sommets, l’algorithme glouton donne une coloration propre optimale
(i.e. avec χ(G) couleurs). (Indication : Supposons que l’algorithme glouton utilise k couleurs avec l’ordre
(v1 < . . . < vn ) et soit i plus petit entier tel qu’il existe une clique composée de k − i + 1 sommets colorés
de i à k. Montrer que i = 1.)
Exercice 5.12 Soient G1 et G2 deux graphes disjoints et x1 y1 ∈ E(G1 ) et x2 y2 ∈ E(G2 ). La somme d’Hajós
G = (G1 , x1 y1 ) + (G2 , x2 y2 ) est le graphe obtenu à partir de G1 ∪ G2 en identifiant x1 et x2 , supprimant
x1 y1 et x2 y2 , et ajoutant y1 y2 . Montrer que χ(G) ≥ min{χ(G1 ), χ(G2 )}. faire un dessin
Exercice 5.13 Dans le plan, on considère un ensemble de carrés C alignés sur les axes et de côté variable.
Le graphe d’intersection de C noté GC est défini comme suit :
- les sommets de GC sont les carrés de C ;
- deux sommets sont reliés si et seulement si les carrés correspondant s’intersectent.
1) Considérons l’ensemble C1 de carrés dessiné ci -dessous. (Pour une meilleure lisibilité, les coins des carrés
ont été noircis.)
a) Dessiner le graphe d’intersection GC1 .
b) Quel est son nombre chromatique ?
2) Soit C un ensemble de carrés quelconques et C le plus petit carré de C.
a) Montrer que le voisinage de C dans GC est contenu dans l’union de 4 ensembles Ni , 1 ≤ i ≤ 4, tels
que pour tout 1 ≤ i ≤ 4, Ni ∪ {C} soit une clique. (On pourra considérer les carrés contenant un coin
de C.)
b) En déduire que χ(GC ) ≤ 4ω(GC ) − 3.
3) On suppose maintenant que les carrés de C sont tous identiques.
a) Montrer que χ(GC ) ≤ 2ω(GC ) − 1. (On pourra considérer le carré le plus haut.)
b) Donner un exemple de graphe G pour lequel χ(GC ) = 3 et ω(GC ) = 2.
Exercice 5.14 Montrer la formule d’Euler : pour un graphe planaire connexe avec n sommets, m arêtes et
f faces,
n−m+f =2
Exercice 5.15 Montrer que si G est un graphe régulier avec un nombre impair de sommets, alors χ 0 (G) =
∆(G) + 1.
Exercice 5.16 Montrer que χ0 (K2n−1 ) = χ0 (K2n ) = 2n − 1.
Exercice 5.17 Soit G un graphe r-régulier biparti et E0 un ensemble de r − 1 arêtes. Montrer que G − E0
possède un couplage parfait.
Exercice 5.18 Le produit de deux graphes G et H est le graphe G × H ayant pour ensemble de sommets
V (G) × V (H) et tel que deux sommets (u, v) et (u0 , v 0 ) sont adjacents si et seulement si u = u0 et vv 0 ∈ E(H)
ou v = v 0 et uu0 ∈ E(G).
(a) Montrer que χ0 (G × K2 ) = ∆(G × K2 ).
(b) En déduire que si H est non trivial avec χ0 (H) = ∆(H) alors χ0 (G × H) = ∆(G × H).
56 CHAPITRE 5. COLORATION DE GRAPHES
