Polynôme chromatique

En mathématiques, plus particulièrement en théorie des graphes, le polynôme chromatique d'un graphe est une fonction comptant les colorations distinctes d'un graphe. Cela donne une fonction polynômiale dépendant du nombre de couleurs autorisé. Il a été introduit d'abord en 1912 pour les graphes planaires, par George David Birkhoff, qui cherchait à démontrer le théorème des quatre couleurs^[1].

Ce polynôme a pour racines tous les entiers positifs ou nuls strictement inférieurs au nombre chromatique du graphe et a pour degré l'ordre du graphe.

Le polynôme chromatique d'un graphe est un invariant, c'est-à-dire une propriété dépendant uniquement de sa structure et indépendante de son étiquetage.

Le terme de chromatiquement équivalent est employé pour désigner des graphes ayant le même polynôme chromatique. A l'opposé, un graphe chromatiquement unique est déterminé par son polynôme chromatique.

Exemples

Les 3 graphes avec un polynôme chromatique égal à
(x − 2)(x − 1)³x

Exemples de polynômes chromatiques

Triangle K3	t(t − 1)(t − 2)
Graphe complet Kn	$t(t-1)(t-2) \dots (t-(n-1))$
Arbre avec n sommets	t(t − 1)n − 1
Graphe cycle Cn	(t − 1)n + ( − 1)n(t − 1)
Graphe de Petersen	t(t − 1)(t − 2)(t7 − 12t6 + 67t5 − 230t4 + 529t3 − 814t2 + 775t − 352)
Graphe singleton	t

• Le graphe diamant est chromatiquement unique : c'est le seul graphe à avoir (x − 2)²(x − 1)x comme polynôme chromatique.
• Il existe deux graphes chromatiquement équivalents au graphe taureau. L'un d'eux est le graphe criquet.

Note et référence

1. ↑ (en) G. D. Birkhoff, « A Determinant Formula for the Number of Ways of Coloring a Map », dans Ann. Math., vol. 14, 1912, p. 42-46 

Liens externes

• (en) Eric W. Weisstein, « Chromatic polynomial », MathWorld
• (en) Chromatic polynomial de PlanetMath
• (en) Code for computing Tutte, Chromatic and Flow Polynomials, par Gary Haggard, David J. Pearce et Gordon Royle