The Dichromatic Polynomial of a Digraph

Let lambda be a positive integer. An acyclic lambda-coloring of a digraph D is a partition of the vertices of D into lambda color clases such that the color classes induce acyclic subdigraphs in D. The minimum integer lambda for which there exists an acyclic lambda-coloring of D is the dichromatic number dc(D) of D. Let P(D; lambda) be the dichromatic polynomial of D, which is the number of acyclic lambda-colorings of D. In this paper, a recursive formula for P(D; lambda) is given. The coefficients of the polynomial P(D; lambda) are studied. The dichromatic polynomial of a digraph D is related to the structure of its underlying graph UG(D). Also, we study dichromatic equivalently and dichromatically unique digraphs.