Bivariate Chromatic Polynomials of Mixed Graphs

DOI10.46298/DMTCS.9595MaRDI QIDQ6505250arXivFDO

Authors Matthias Beck, Sampada Kolhatkar

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Graph polynomials (05C31) Coloring of graphs and hypergraphs (05C15) Combinatorics of partially ordered sets (06A07)

Abstract: The bivariate chromatic polynomial $ch{i}_G(x,y)$ of a graph $G=(V,E)$, introduced by Dohmen-P"{o}nitz-Tittmann (2003), counts all $x$-colorings of $G$ such that adjacent vertices get different colors if they are $ley$. We extend this notion to mixed graphs, which have both directed and undirected edges. Our main result is a decomposition formula which expresses $ch{i}_G(x,y)$ as a sum of bivariate order polynomials (Beck-Farahmand-Karunaratne-Zuniga Ruiz 2020), and a combinatorial reciprocity theorem for $ch{i}_G(x,y)$.

This page was built for publication: Bivariate Chromatic Polynomials of Mixed Graphs

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