Bivariate Chromatic Polynomials of Mixed Graphs

Abstract

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

10 pages, 3 figures, To appear in DMTCS vol.25:2 #2 (2023)

References in corpus (5)

• Gelfand-Tsetlin polytopes and Feigin-Fourier-Littelmann polytopes as marked poset polytopes
• Fibonacci Identities and Graph Colorings
• Closed-form expansions for the universal edge elimination polynomial
• Enumeration of Golomb Rulers and Acyclic Orientations of Mixed Graphs
• On Weak Chromatic Polynomials of Mixed Graphs