A bivariate chromatic polynomial for signed graphs

Abstract

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

8 pages, 4 figures

References in corpus (2)

• Fibonacci Identities and Graph Colorings
• Closed-form expansions for the bivariate chromatic polynomial of paths and cycles