A bivariate chromatic polynomial for signed graphs

We study Dohmen--Pönitz--Tittmann's bivariate chromatic polynomial $c_Γ(k,l)$ which counts all $(k+l)$-colorings of a graph $Γ$ such that adjacent vertices get different colors if they are $\le k$. Our first contribution is an extension of $c_Γ(k,l)$ 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 $c_Γ(k,l)$ and its signed-graph analogues, reminiscent of Stanley's reciprocity theorem linking chromatic polynomials to acyclic orientations.

No reviews yet.

No comments yet.