We found a match
Your institution may have rights to this item. Sign in to continue.
- Title
The Dichromatic Polynomial of a Digraph.
- Authors
González-Moreno, D.; Hernández-Ortiz, R.; Llano, B.; Olsen, M.
- Abstract
Let λ be a positive integer. An acyclic λ -coloring of a digraph D is a partition of the vertices of D into λ color clases such that the color classes induce acyclic subdigraphs in D. The minimum integer λ for which there exists an acyclic λ -coloring of D is the dichromatic numberdc(D) of D. Let P (D ; λ) be the dichromatic polynomial of D, which is the number of acyclic λ -colorings of D. In this paper, a recursive formula for P (D ; λ) is given. The coefficients of the polynomial P (D ; λ) 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.
- Publication
Graphs & Combinatorics, 2022, Vol 38, Issue 3, p1
- ISSN
0911-0119
- Publication type
Article
- DOI
10.1007/s00373-022-02484-0