Universit Paris 13
Institut Galile
Sup Galile INFO2
Anne 2011-2012
Algorithmique de Graphes
TD4 : Coloration
Exercice 1
Une usine chimique fabrique sept produits A, B, C, D, E, F et G. Le stockage dans un mme
entrept de certains dentre eux peut poser des problmes. Le tableau suivant indique les incompatibilits de stockage. La lettre "i" signifie incompatible.
B C D E F G
A i
i
1. Modliser cette situation laide dun graphe G.
B
i
i
i
2. Quel est le nombre minimum dentrepts ncessaires
C
i
i
i
cette entreprise ?
D
i
i
E
i
F
i
Exercice 2
Un graphe est dit p-colorable sil peut tre color par q couleurs, q p. Le plus petit entier m
tel que le graphe G soit m-colorable sappelle le nombre chromatique de G et est not (G).
Donner le nombre chromatique des graphes suivants :
Exercice 3
Si G = (V, E) est un graphe, on note par (G) la cardinalit maximale dun stable dans G.
p
Montrer que si G = (V, E) est un graphe tel que |V | = p, alors (G)
(G) p + 1 (G).
Exercice 4
Appliquer lalgorithme squentiel pour dterminer une coloration pour les graphes suivants :
v1
v5
v3
v3
v9
v2
v4
v4
v1
v5
v8
v6
v7
v2
v6
v10
v7
v8
v11
Exercice 5
Donner un graphe G (le plus petit possible) pour lequel lalgorithme squentiel donne un
nombre de couleurs strictement suprieur (G).
1
Exercice 6
Soient G1 , . . . , Gn des graphes 2 2 disjoints. Soit G = G1 + . . . + Gn le graphe obtenu partir
de G1 , . . . , Gn en ajoutant une arte entre chaque paire de sommets appartenant des graphes
diffrents.
On note par (G), le nombre maximum de sommets dune clique dans G.
Exemple :
G1
G1 + G2
G2
Montrer que (G) =
Pn
i=1 (Gi )
et (G) =
Pn
i=1 (Gi ).
Exercice 7
On dsire colorer les artes de telle manire que 2 artes adjacentes naient pas la mme couleur.
Un graphe G est dit n-arte colorable si les artes peuvent tre colores par m couleurs avec
m n. Le plus petit entier m tel que G soit m-arte colorable est appel le nombre artechromatique de G et not 1 (G).
On note par (G), le degr maximum de G. Un graphe G est dit de classe 1 si 1 (G) = (G)
et de classe 2 si 1 (G) = (G) + 1. Un graphe G = (V, E) ayant au moins 2 artes est dit
classe-minimal si G est de classe 2 et G e est de classe 1 pour tout e E.
1. Si G1 et G2 sont deux graphes de classe 1 et H est un graphe tel que G1 H G2 , H
est-il ncessairement de classe 1. (H G si et seulement si H est un sous-graphe induit
de G).
2. (a) Les graphes suivants sont-ils de classe 2 ?
(b) Montrer que les deux graphes dordre 5 (cest--dire possdant 5 sommets) sont
classe-minimaux.
Exercice 8
Une coloration totale dun graphe G est une affectation de couleurs aux sommets et aux artes
du graphe de telle manire que deux lments adjacents et deux lments incidents nont pas
la mme couleur.
Le nombre minimum de couleurs ncessaires pour une coloration totale de G est appel le
nombre chromatique total de G et not 2 (G).
La conjecture suivante est connue sous le nom de conjecture de coloration totale :
2 (G) 2 + (G).
1. Montrer que 2 (G) 1 + (G) pour tout graphe G.
2. Vrifier la conjecture de coloration totale pour les graphes G tels que (G) 2.
3. Dterminer (G), 1 (G) et 2 (G) pour le premier graphe de lexercice 7.
2
Universit Paris 13
Institut Galile
Sup Galile INFO2
Anne 2011-2012
Algorithmique de Graphes
TD4 : Coloration
v1
v5
v3
v3
v9
v2
v4
v1
v8
v6
v4
v5
v7
v2
v6
v8
v7
v10
v11
