Université Paris 13 Sup Galilée INFO2Institut Galilée Année 2011-2012

Algorithmique de GraphesTD4 : Coloration

Exercice 1Une usine chimique fabrique sept produits A, B, C, D, E, F et G. Le stockage dans un mêmeentrepôt de certains d’entre eux peut poser des problèmes. Le tableau suivant indique les in-compatibilités de stockage. La lettre "i" signifie incompatible.

B C D E F G

A i i

B i i i

C i i i

D i i

E i

F i

1. Modéliser cette situation à l’aide d’un graphe G.

2. Quel est le nombre minimum d’entrepôts nécessaires àcette entreprise ?

Exercice 2Un graphe est dit p-colorable s’il peut être coloré par q couleurs, q ≤ p. Le plus petit entier m

tel que le graphe G soit m-colorable s’appelle le nombre chromatique de G et est noté χ(G).Donner le nombre chromatique des graphes suivants :

Exercice 3Si G = (V,E) est un graphe, on note par β(G) la cardinalité maximale d’un stable dans G.Montrer que si G = (V,E) est un graphe tel que |V | = p, alors p

β(G) ≤ χ(G) ≤ p + 1 − β(G).

Exercice 4Appliquer l’algorithme séquentiel pour déterminer une coloration pour les graphes suivants :

v2

v1

v3 v5

v8v4 v6

v7v11

v8v7

v1

v9v2

v3

v4 v6

v5

v10

Exercice 5Donner un graphe G (le plus petit possible) pour lequel l’algorithme séquentiel donne unnombre de couleurs strictement supérieur à χ(G).

1

Exercice 6Soient G1, . . . , Gn des graphes 2 à 2 disjoints. Soit G = G1 + . . .+Gn le graphe obtenu à partirde G1, . . . , Gn en ajoutant une arête entre chaque paire de sommets appartenant à des graphesdifférents.On note par ω(G), le nombre maximum de sommets d’une clique dans G.

G1 + G2

Exemple :

G2

G1

Montrer que χ(G) =∑n

i=1 χ(Gi) et ω(G) =∑n

i=1 ω(Gi).

Exercice 7On désire colorer les arêtes de telle manière que 2 arêtes adjacentes n’aient pas la même couleur.Un graphe G est dit n-arête colorable si les arêtes peuvent être colorées par m couleurs avecm ≤ n. Le plus petit entier m tel que G soit m-arête colorable est appelé le nombre arête-

chromatique 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 arêtes est ditclasse-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 nécessairement de classe 1. (H ⊂ G si et seulement si H est un sous-graphe induitde G).

2. (a) Les graphes suivants sont-ils de classe 2 ?

(b) Montrer que les deux graphes d’ordre 5 (c’est-à-dire possédant 5 sommets) sontclasse-minimaux.

Exercice 8Une coloration totale d’un graphe G est une affectation de couleurs aux sommets et aux arêtesdu graphe de telle manière que deux éléments adjacents et deux éléments incidents n’ont pasla même couleur.Le nombre minimum de couleurs nécessaires pour une coloration totale de G est appelé lenombre 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. Vérifier la conjecture de coloration totale pour les graphes G tels que ∆(G) ≤ 2.

3. Déterminer χ(G), χ1(G) et χ2(G) pour le premier graphe de l’exercice 7.

2

Université Paris 13 Sup Galilée INFO2Institut Galilée Année 2011-2012

Algorithmique de GraphesTD4 : Coloration

v2

v1

v3 v5

v8v4 v6

v7

v11

v8v7

v1

v9v2

v3

v4 v6

v5

v10