Orientations Acycliques et le Polynôme Chromatique

On attache à tout graphe G son polynôme chromatiqueχG (λ), qui dénombre ses colorations régulières avecλ couleurs. D’après Stanley, on sait que |χ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χG (λ) développé en puissances de λ et surtout en puissances de (λ − 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 βGde Crapo. Cet article donne également un nouvel éclat aux résultats classiques de Cartier, Foata, Viennot, Brenti, Gessel et Stanley. The chromatic polynomialχG (λ), which is associated with each graph G, enumerates its regular colorations with λ colors. Stanley showed that |χG ( − 1)| is equal to the number of acyclic orientations of the graph, a result that was refined by Greene and Zaslavsky. The purpose of the paper is to show that a further refinement can be obtained by interpreting each coefficient of χG(λ), when the polynomial is developed with respect to powers of λ and (λ − 1). A systematic use of the generating functions for set functions enables us to have very short and instructive proofs. Gebhard and Sagan, who had already found combinatorial proofs of two results by Greene and Zaslavsky, suggested that further proofs were to be found. Finally, the set functions algebra allows us to establish a series of new interpretations for Crapo’sβG invariant. This paper also brings a new light to the classical results due to Cartier, Foata, Viennot, Brenti, Gessel and Stanley.