A bivariate chromatic polynomial for signed graphs

Details A bivariate chromatic polynomial for signed graphs A bivariate chromatic polynomial for signed graphs

2012-04-11

arxiv.org/abs/1204.2568v1

Mathematics

Combinatorics

7 pages, 2 figures

Scientific paper

We study Dohmen--P\"onitz--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.

Affiliated with

Also associated with

No associations

Rating

A bivariate chromatic polynomial for signed graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A bivariate chromatic polynomial for signed graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A bivariate chromatic polynomial for signed graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-311347