Mixed Graph Colorings

Modeling of metabolic pathways in biology and process management in operating systems are applications of mixed graphs. A mixed graph is a graph with directed edges, called arcs, and undirected edges. The strong (weak) chromatic polynomial of a mixed graph is a counting function that counts proper k-colorings, that is, assigning colors to vertices such that colors are different on vertices connected by an edge, while colors have to obey the < (≤) along an arc. We find a contraction-deletion analogue for mixed graphs in which the weak chromatic polynomial of any mixed graph can be reduced to a linear combination of weak chromatic polynomials of simpler mixed graphs, such as trees. Following closely previous work on reciprocity theorems for other types of chromatic polynomials, we also investigate a reciprocity theorem for weak chromatic polynomials from the standpoint of inside-out polytopes and partially ordered sets.