GR-BThéorie des graphes

Sous-graphe complet et nombre chromatique

Idée directrice

Le nombre chromatique $\gamma(G)$ est borné par l'ordre du plus grand sous-graphe complet et par $1+\Delta$ ( $\Delta$ = degré maximal). Une coloration explicite (souvent type Welsh-Powell) fixe ensuite la valeur exacte. Attesté 2018, 2021, 2022.

Signature de reconnaissance — l'énoncé se trahit ainsi

« nombre chromatique du graphe »

« sous graphe complet »

« montrer que 3 ≤ γ ≤ 5 »

Sujet principal

Exercice — coloration d'un réseau d'appareils

3 questionsCorrigé masqué

Soit le graphe non orienté $G$ de sommets $A,B,C,D,E$ et d'arêtes $AB,AC,BC,BD,CD,CE,DE$ .

Dresser le tableau des degrés des sommets.
Exhiber un sous-graphe complet d'ordre $3$ . En déduire une minoration de $\gamma(G)$ .
En utilisant $\Delta=\max\deg$ et une coloration explicite, déterminer le nombre chromatique $\gamma(G)$ .

Voir la correction commentéeAprès avoir posé votre démarche

1. On a : $\deg(A)=2$ ( $AB,AC$ ), $\deg(B)=3$ ( $AB,BC,BD$ ), $\deg(C)=4$ ( $AC,BC,CD,CE$ ), $\deg(D)=3$ ( $BD,CD,DE$ ), $\deg(E)=2$ ( $CE,DE$ ).

2. On pose le sous-graphe induit par $\{B,C,D\}$ : les arêtes $BC,BD,CD$ existent toutes. C'est un sous-graphe complet d'ordre $3$ . D'où $\gamma(G)\ge3$ .

3. On a : $\Delta=4$ , donc $\gamma(G)\le\Delta+1=5$ . Coloration : $C$ en couleur $c_1$ ; $B$ et $E$ en $c_2$ ; $A$ et $D$ en $c_3$ . Les sommets adjacents reçoivent des couleurs distinctes. Par suite $\gamma(G)=3$ (on a $3\le\gamma(G)\le5$ et une coloration propre à $3$ couleurs).

Exercices d'entraînement — une nuance à la fois

Entraînement 01 / 02

Drill GR-B.1 — Encadrement du nombre chromatique

2 questionsCorrigé masqué

Soit un graphe connexe $G$ d'ordre $6$ avec $\Delta=3$ et un sous-graphe complet d'ordre $3$ .

Montrer que $3\le\gamma(G)\le4$ .
Pourquoi un sous-graphe complet d'ordre $3$ force-t-il au moins trois couleurs ?

Voir la correction commentéeAprès avoir posé votre démarche

1. On a : la présence d'un sous-graphe complet d'ordre $3$ donne $\gamma(G)\ge3$ . D'autre part $\gamma(G)\le\Delta+1=4$ . Par suite $3\le\gamma(G)\le4$ .

2. Dans un sous-graphe complet, tous les sommets sont deux à deux adjacents : chacun exige une couleur distincte. Trois sommets mutuellement adjacents imposent donc trois couleurs au minimum.

Entraînement 02 / 02

Drill GR-B.2 — Coloration à deux couleurs

2 questionsCorrigé masqué

Soit le graphe cycle $C_4$ : sommets $A,B,C,D$ , arêtes $AB,BC,CD,DA$ .

Quel est le degré de chaque sommet ?
Proposer une coloration propre et en déduire $\gamma(C_4)$ .

Voir la correction commentéeAprès avoir posé votre démarche

1. On a : chaque sommet du cycle $C_4$ est incident à exactement deux arêtes, donc degré $2$ .

2. On colorie $A$ et $C$ en couleur $c_1$ , $B$ et $D$ en couleur $c_2$ . Aucune arête ne joint deux sommets de même couleur, donc la coloration est propre. Comme le graphe possède au moins une arête, une seule couleur ne suffit pas. Par suite le nombre chromatique vaut $\gamma(C_4)=2$ .

Méthode / Automatismes

Minorer $\gamma$ par l'ordre du plus grand sous-graphe complet (clique).
Majorant usuel : $\gamma\le\Delta+1$ .
Conclure par une coloration réelle (pas seulement l'encadrement).

Pièges classiques

Prendre un triangle non induit. Confondre nombre chromatique et degré maximal. S'arrêter à l'encadrement sans coloration.