Bivariate Chromatic Polynomials of Mixed Graphs
| Autor: | Beck, Matthias, Kolhatkar, Sampada |
|---|---|
| Rok vydání: | 2021 |
| Předmět: | |
| Zdroj: | Discrete Mathematics & Theoretical Computer Science, vol. 25:2, Combinatorics (November 17, 2023) dmtcs:9595 |
| Druh dokumentu: | Working Paper |
| DOI: | 10.46298/dmtcs.9595 |
| Popis: | The bivariate chromatic polynomial $\chi_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 $\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)$. Comment: 10 pages, 3 figures, To appear in DMTCS vol.25:2 #2 (2023) |
| Databáze: | arXiv |
| Externí odkaz: |
|