Groupe d’études et de recherche en analyse des décisions

Nombre de colorations non équivalentes d'un graphe

Hadrien Mélot Université de Mons, Belgique

Quel est le nombre total de colorations valides possibles pour un graphe \(G\) d'ordre \(n\) ? Depuis plus d'un siècle, la réponse classique à cette question est liée à la notion du polynôme chromatique qui a été introduite par Birkhoff en 1912. Soit \(Pi(G, k)\) le nombre de colorations de \(G\) utilisant au plus \(k\) couleurs, en comptant comme distinctes deux colorations identiques par permutation l'une de l'autre. Le polynôme chromatique est le polynôme de degré \(n\) passant par les points \((k, Pi(G, k))\) pour \(k = 0, 1,... , n\). Le nombre de colorations est aujourd'hui communément interprété comme étant \(Pi(G, n)\). Nous soutenons que le nombre de colorations non-équivalentes (au sens des permutations) et utilisant un nombre exact \(k\) de couleurs est également intéressant. C'est particulièrement vrai quand un ensemble d'éléments doit être partitionné en \(k\) sous-ensembles non vides et sujets à certaines contraintes.

Dans cet exposé, nous définissons formellement \(P(G)\) comme étant le nombre total de colorations non-équivalentes d'un graphe \(G\) et nous montrons les similarités et les différences entre cet invariant et le polynôme chromatique. Ensuite, nous posons le problème du calcul de \(P(G)\) et nous en donnons quelques valeurs exactes pour certains graphes particuliers. Enfin, nous prouvons certaines bornes sur \(P(G)\) pour des graphes ayant un degré maximum borné et nous mentionnons quelles autres bornes restent des problèmes ouverts.

(Travail conjoint avec Alain Hertz, GERAD)