Coloriage de graphes — nombre chromatique | Riyaddiyat

Énoncé du problème

Le nombre chromatique χ(G) d'un graphe G est le nombre minimal de couleurs nécessaires pour colorier les sommets de G de sorte que deux sommets adjacents aient des couleurs différentes.

Montrer que χ(G) ≥ 2 si et seulement si G contient au moins une arête.
Montrer que χ(G) = 2 si et seulement si G est biparti et non vide (ne contient pas de cycle impair).
Le graphe complet K_n (n sommets tous reliés entre eux) — quel est son nombre chromatique ?
Application : une ville a 5 quartiers. Les quartiers 1-2, 1-3, 2-3, 3-4, 4-5 ont des frontières communes. Combien de couleurs faut-il pour colorier la carte ?

1. Si G contient une arête {u,v}, alors u et v doivent avoir des couleurs différentes → χ ≥ 2. Si G n'a pas d'arête, une seule couleur suffit → χ = 1. ✓

2. Un graphe est biparti si ses sommets se divisent en deux groupes A et B sans arête interne. On colorie A en rouge, B en bleu → χ = 2. Réciproquement, si χ = 2, les deux ensembles de couleurs forment une bipartition. Un graphe biparti ne contient pas de cycle de longueur impaire. ✓

3. Dans K_n, tout sommet est adjacent à tous les autres → tous doivent avoir des couleurs différentes → χ(K_n) = n.

4. Représentons par un graphe : sommets = quartiers, arêtes = frontières. Arêtes : 1-2, 1-3, 2-3 forment K₃ (triangle) → χ ≥ 3. On peut colorier : 1=rouge, 2=bleu, 3=vert, 4=rouge (voisin de 3), 5=bleu (voisin de 4). χ = 3 couleurs suffisent.

Coloriage de graphes — nombre chromatique

Énoncé du problème

Solution détaillée