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. Autrement dit, deux graphes isomorphes auront le même polynôme chromatique.
Le terme de chromatiquement équivalent est employé pour désigner des graphes ayant le même polynôme chromatique. À l'opposé, un graphe chromatiquement unique est déterminé par son polynôme chromatique.
Définition
Soit G un graphe ayant n sommets. Notant le nombre de colorations des sommets de G avec k couleurs (distinctes), le polynôme chromatique de G, , est défini comme étant l'unique polynôme d'interpolation de degré n tel que, pour tout k avec , on ait . On a en particulier, pour tout graphe ayant plus d'une arête, , et plus précisément, le nombre chromatique de g est le plus petit entier qui n'est pas une racine de .
Un théorème d'intérêt est le suivant : pour toute arête e du graphe G, où G-e est le graphe G sans l'arête e et G.e le graphe obtenu en contractant l'arête e de G.
Un corollaire de ce théorème a été énoncé par George David Birkhoff en 1912 :
Pour un graphe G à n nœuds, est un polynôme monique de degré n (i.e. un polynôme dont le coefficient du terme de degré n vaut 1), de terme constant nul et dont les coefficients alternent en signe.