Le plus petit entier k tel que les sommets d'un graphe peuvent être coloriés avec k couleurs de manière que deux sommets adjacents n'aient pas la même couleur (coloration propre des sommets).

Principe

Le nombre chromatique mesure la manière dont un graphe peut être partitionné en ensembles indépendants : c'est le nombre minimal de classes de couleurs nécessaires pour que chaque classe soit un ensemble indépendant.

Démonstration

Un graphe complet à n sommets a nombre chromatique n. Tout graphe bipartite non vide a nombre chromatique 2. Un cycle impair C_{2m+1} a nombre chromatique 3.

Mauvaise application

Confondre le nombre chromatique des sommets avec l'indice chromatique des arêtes, ou avec les nombres chromatiques fractionnaire ou par listes, ou supposer que des bornes naïves (comme χ ≤ Δ+1) sont des égalités sans vérifier les exceptions (théorème de Brooks).

Conséquence

Le nombre chromatique contraint les colorations dans des problèmes d'ordonnancement ou d'allocation de registres, renseigne sur la structure de cliques (la taille maximale d'une clique est une borne inférieure) et est difficile à calculer (décision NP-difficile pour k≥3).

Inversion

La notion inverse autorise des colorations impropres qui permettent des couleurs identiques sur des sommets adjacents, réduisant le nombre de couleurs requis ; la taille d'un recouvrement par cliques ou le nombre d'indépendance offrent des mesures alternatives.

Limite

Défini pour graphes finis et infinis (où le nombre chromatique peut être infini) ; pour graphes orientés et hypergraphes les notions analogues diffèrent et nécessitent des définitions adaptées (nombre chromatique orienté, colorations d'hypergraphes).

Tension sémantique

Tension entre nombre chromatique et nombre de cliques (borne inférieure), polynôme chromatique (qui compte les colorations) et nombres chromatiques fractionnaire ou par listes qui raffinent ou relâchent la définition et peuvent diverger de χ.

Synthèse

Le nombre chromatique est le nombre minimal de classes d'indépendance de sommets nécessaires pour une coloration propre ; il mesure la complexité combinatoire essentielle d'un graphe et interagit avec cliques, degrés et variantes de coloration.