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 questionsFigure fournieCorrigé 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. Idée : compter les arêtes incidentes. $\deg A=2$ , $\deg B=3$ , $\deg C=4$ , $\deg D=3$ , $\deg E=2$ (somme $14=2\times7$ arêtes).

2. Idée : dans une clique, tous les sommets sont deux à deux adjacents et exigent des couleurs distinctes. $BC$ , $BD$ , $CD$ existent : $\{B,C,D\}$ est un sous-graphe complet d'ordre $3$ , donc $\gamma(G)\geq3$ .

3. Idée : majorer par $\Delta+1$ , puis exhiber une coloration atteignant la minoration. $\Delta=4$ donne $\gamma(G)\leq5$ . Coloration : $C\to c_1$ ; $B,E\to c_2$ (non adjacents) ; $A,D\to c_3$ (non adjacents). Chaque arête joint deux couleurs différentes : trois couleurs suffisent, donc $\boxed{\gamma(G)=3}$ .

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. Idée : encadrement classique. La clique d'ordre $3$ donne $\gamma(G)\geq3$ ; le degré maximal donne $\gamma(G)\leq\Delta+1=4$ . Donc $3\leq\gamma(G)\leq4$ .

2. Idée : adjacence deux à deux. Dans un sous-graphe complet d'ordre $3$ , chaque sommet est voisin des deux autres ; deux d'entre eux ne peuvent jamais partager une couleur, d'où trois couleurs au moins.

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. Idée : un cycle, deux arêtes par sommet. Tous les sommets de $C_4$ ont pour degré $2$ .

2. Idée : alterner les couleurs le long du cycle pair. $A,C\to c_1$ et $B,D\to c_2$ : les voisins de $A$ sont $B$ et $D$ , colorés $c_2$ , etc. La coloration est propre ; une seule couleur est impossible dès qu'il y a une arête. Donc $\gamma(C_4)=2$ (un cycle de longueur impaire aurait besoin de trois couleurs).

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.