Acyclic Orientations and the Chromatic Polynomial of Signed Graphs

2022/09/03 by Jiyang Gao, Gao, Jiyang
Mathematics · #05C15 #05C31 #Advanced Combinatorial Mathematics #Combinatorics (math.CO) #FOS: Mathematics

paper · pdf · doi:10.48550/arxiv.2209.01303

openalex publication_date 2022/09/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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 χ_G(k,l) that counts the number of signed colorings using colors 0,±1,…,± k along with l-1 symmetric colors 0₁,…,0_l-1. We show that the evaluation of the bivariate chromatic polynomial |χ_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.

Related

• An Extension of Stanley's Symmetric Acyclicity Theorem to Signed Graphs
• Sinks in Acyclic Orientations of Graphs
• Acyclic orientation polynomials and the sink theorem for chromatic symmetric functions
• Unlabeled Signed Graph Coloring
• The chromatic number of a signed graph