Acyclic orientations of graphs Original Research Article

Let image be a finite graph with image vertices and image its chromatic polynomial. A combinatorial interpretation is given to the positive integer image, where image is a positive integer, in terms of acyclic orientations of image. In particular, image is the number of acyclic orientations of image. 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.