On Weak Chromatic Polynomials of Mixed Graphs

Abstract

A 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 uν is an edge, and the color of u is less than or equal to (resp. strictly less than) the color of ν if uν 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.

Files

Additional details