Acyclic Orientations and the Chromatic Polynomial of Signed Graphs

Publication date 2 September 2022

Coloring of graphs and hypergraphs (05C15) Graph polynomials (05C31)

Abstract: We present a new correspondence between acyclic orientations and coloring of a signed graph (symmetric graph). Goodall et al. introduced a bivariate chromatic polynomial

c h i_{G} (k, l)

that counts the number of signed colorings using colors

0, p m 1, d o t s, p m k

along with

l - 1

symmetric colors

0_{1}, d o t s, 0_{l - 1}

. We show that the evaluation of the bivariate chromatic polynomial

| c h i_{G} (- 1, 2) |

is equal to the number of acyclic orientations of the signed graph modulo the equivalence relation generated by swapping sources and sinks. We present three proofs of this fact, a proof using toric hyperplane arrangements, a proof using deletion-contraction, and a direct proof.

This page was built for publication: Acyclic Orientations and the Chromatic Polynomial of Signed Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6409619)