Matthias Beck ; Sampada Kolhatkar - Bivariate Chromatic Polynomials of Mixed Graphs

dmtcs:9595 - Discrete Mathematics & Theoretical Computer Science, November 17, 2023, vol. 25:2 - https://doi.org/10.46298/dmtcs.9595
Bivariate Chromatic Polynomials of Mixed GraphsArticle

Authors: Matthias Beck ; Sampada Kolhatkar

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


    Volume: vol. 25:2
    Section: Combinatorics
    Published on: November 17, 2023
    Accepted on: June 1, 2023
    Submitted on: May 23, 2022
    Keywords: Mathematics - Combinatorics,05C15 (Primary), 05A15, 06A07, 05C31 (Secondary)

    Consultation statistics

    This page has been seen 255 times.
    This article's PDF has been downloaded 124 times.