Bivariate Chromatic Polynomials of Mixed Graphs

DOI10.46298/DMTCS.9595arXiv2111.09384MaRDI QIDQ6505250FDOQ6505250

Authors: Matthias Beck, Sampada Kolhatkar 

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)$.

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)

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)