On Weak Chromatic Polynomials of Mixed Graphs

Abstract

A \emph{mixed graph} is a graph with directed edges, called arcs, and undirected edges. A $k$-coloring of the vertices is proper if colors from $1,2,...,k$ are assigned to each vertex such that $u$ and $v$ have different colors if $uv$ is an edge, and the color of $u$ is less than or equal to (resp. strictly less than) the color of $v$ if $uv$ is an arc. The weak (resp. strong) chromatic polynomial of a mixed graph counts the number of proper $k$-colorings. Using order polynomials of partially ordered sets, we establish a reciprocity theorem for weak chromatic polynomials giving interpretations of evaluations at negative integers.

6 pages, 2 figures, to appear in Graphs & Combinatorics