European Journal of Combinatorics, t. 22, p. 1101-1123, 2001.

Bodo Lass

Orientations acycliques et le polynôme chromatique

Résumé. On attache à tout graphe G son polynôme chromatique X(G,c), qui dénombre ses colorations régulières avec c couleurs. D'après Stanley, on sait que |X(G,-1)| est égal au nombre d'orientations acycliques du graphe, un résultat qui fut raffiné par Greene et Zaslavsky. Nous nous proposons de l'affiner davantage en interprétant, avec l'aide de certaines orientations acycliques, les coefficients de X(G,c) développé en puissances de c et surtout en puissances de (c-1). L'utilisation systématique des fonctions génératrices des fonctions d'ensembles permet d'avoir des démonstrations très courtes et explicatives. Elles se veulent une réponse à la suggestion faite par Gebhard et Sagan, qui ont déjà trouvé des démonstrations combinatoires de deux résultats de Greene et Zaslavsky. Les fonctions d'ensembles permettent aussi d'établir une série d'interprétations nouvelles de l'invariant beta(G) de Crapo. Cet article donne également un nouvel éclat aux résultats classiques de Cartier, Foata, Viennot, Brenti, Gessel et Stanley.

Les versions suivantes sont disponibles :

Version du journal :

pdf version (245K)

Une version courte est disponible dans :

Commutation and Rearrangements,

An electronic reedition of the monograph «Problèmes combinatoires de commutation et réarrangements» by Pierre Cartier and Dominique Foata (originally published in Lecture Notes in Mathematics, 85, Berlin, Springer-Verlag, 1969) with three new appendices by D. Foata, B. Lass and Ch. Krattenthaler.