Nombre chromatique

Postbac

Définition
Soit G un graphe.
On appelle nombre chromatique de G le nombre minimum de couleurs, noté χ ( G ) , nécessaire pour colorier chaque sommet du graphe G de façon que deux sommets adjacents quelconques soient de couleurs différentes.

Théorème
Soit d le plus grand degré des sommets d'un graphe G et χ ( G ) le nombre chromatique de ce graphe.
On a : χ ( G ) d + 1 .

Exemple

Rubriques connexes

Graphe complet
Graphe connexe
Graphe non orienté
Sous-graphe

Pages interactives

182   Coloriage et nombre chromatique d'un graphe simple non orienté Outil
Postbac