Polynôme chromatique

En mathématiques, plus particulièrement en théorie des graphes, le polynôme chromatique d'un graphe est une fonction polynômiale donnant le nombre de colorations distinctes d'un graphe, en fonction du nombre de couleurs autorisées. 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. 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 c G ( k ) {\displaystyle c_{G}(k)} le nombre de colorations des sommets de G avec k couleurs (distinctes), le polynôme chromatique de G, P G {\displaystyle P_{G}} , est défini comme étant l'unique polynôme d'interpolation de degré n tel que, pour tout k avec 0 ≤ k ≤ n {\displaystyle 0\leq k\leq n} , on ait P G ( k ) = c G ( k ) {\displaystyle P_{G}(k)=c_{G}(k)} . On a en particulier, pour tout graphe ayant plus d'une arête, P G ( 0 ) = P G ( 1 ) = 0 {\displaystyle P_{G}(0)=P_{G}(1)=0} , et plus précisément, le nombre chromatique de g est le plus petit entier qui n'est pas une racine de P G {\displaystyle P_{G}} .

Un théorème d'intérêt est le suivant : pour toute arête e du graphe G, P G ( k ) = P G − e ( k ) − P G . e ( k ) {\displaystyle P_{G}(k)=P_{G-e}(k)-P_{G.e}(k)} 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, P G ( k ) {\displaystyle P_{G}(k)} 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.

Exemples

Les 3 graphes avec un polynôme chromatique égal à
( x − 2 ) ( x − 1 ) 3 x {\displaystyle (x-2)(x-1)^{3}x}
Exemples de polynômes chromatiques
Triangle K 3 {\displaystyle K_{3}} t ( t − 1 ) ( t − 2 ) {\displaystyle t(t-1)(t-2)}
Graphe complet K n {\displaystyle K_{n}} t ( t − 1 ) ( t − 2 ) … ( t − ( n − 1 ) ) {\displaystyle t(t-1)(t-2)\dots (t-(n-1))}
Arbre avec n {\displaystyle n} sommets t ( t − 1 ) n − 1 {\displaystyle t(t-1)^{n-1}}
Graphe cycle C n {\displaystyle C_{n}} ( t − 1 ) n + ( − 1 ) n ( t − 1 ) {\displaystyle (t-1)^{n}+(-1)^{n}(t-1)}
Graphe de Petersen t ( t − 1 ) ( t − 2 ) ( t 7 − 12 t 6 + 67 t 5 − 230 t 4 + 529 t 3 − 814 t 2 + 775 t − 352 ) {\displaystyle t(t-1)(t-2)(t^{7}-12t^{6}+67t^{5}-230t^{4}+529t^{3}-814t^{2}+775t-352)}
Graphe singleton t {\displaystyle t}
  • Le graphe diamant est chromatiquement unique : c'est le seul graphe à avoir ( x − 2 ) 2 ( x − 1 ) x {\displaystyle (x-2)^{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.

Notes et références

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

Liens externes

  • icône décorative Portail de l'informatique théorique