A Bivariate Chromatic Polynomial for Signed Graphs

摘要

We study Dohmen-Ponitz-Tittmann's bivariate chromatic polynomial which counts all -colorings of a graph such that adjacent vertices get different colors if they are . Our first contribution is an extension of to signed graphs, for which we obtain an inclusion-exclusion formula and several special evaluations giving rise, e.g., to polynomials that encode balanced subgraphs. Our second goal is to derive combinatorial reciprocity theorems for and its signed-graph analogues, reminiscent of Stanley's reciprocity theorem linking chromatic polynomials to acyclic orientations.