Acyclic orientations of graphs

✍ Scribed by Richard P. Stanley

• Publisher: Elsevier Science
• Year: 1973
• Tongue: English
• Weight: 708 KB
• Volume: 5
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(73)90108-8

✦ Synopsis

Let G be a finite graph with p vertices and x its chromatic polynomial. A combinatorial interpretation is given to the positive integer (-l)px(-A),

where h is a positive integer, in terms of acyclic orientations of G. In particular, (-l)Px(-1) is the number of acyclic orientations of G. An application is given to the enumeration of labeled acyclic digraphs. An algebra of full binomial type, in the sense of Doubilet-Rota-Stanley, is constructed which yields the generating functions which occur in the above context.

8. The chromatic polynomial with negative arguments

Let G be a finite graph, which we assume to be without loops or multipk edges. Let V = V(G) denote the set of vertices of G and X = X(G) the set of edges. An edge e E X is thought of as an unordered pair {u, u) of two distinct vertices. The integers p and q denote the cardinalities of V and X, respectively. An orientation of G is an assignment of a direction to each edge {u, u), denoted by u + u or u + u, as the case may be. An orientation of G is said to be acyck if it has no directed cycles.

Let x (X) = x(G, X) denote the chromatic polynomial of G evaluated at X E C. If X is a non-negative integer, then x(X) has the following rather unorthodox interpretation. Proposition 1 A. x(X) is equal to the number of pairs (u, (I), where u is any map 0: I/+ {1,2,..., A) and 0 is an orientation of G, subject to the two conditions: . (a) The orientation 0 is acyclic. (b) If u + u in the orientc:!ion 0, then (T(U) > (J(U).