Bivariate Chromatic Polynomials of Mixed Graphs
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2021
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866909103620620288 |
|---|---|
| author | Beck, Matthias Kolhatkar, Sampada |
| author_facet | Beck, Matthias Kolhatkar, Sampada |
| contents | The bivariate chromatic polynomial $χ_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 $χ_G(x,y)$ as a sum of bivariate order polynomials (Beck-Farahmand-Karunaratne-Zuniga Ruiz 2020), and a combinatorial reciprocity theorem for $χ_G(x,y)$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2111_09384 |
| institution | arXiv |
| publishDate | 2021 |
| record_format | arxiv |
| spellingShingle | Bivariate Chromatic Polynomials of Mixed Graphs Beck, Matthias Kolhatkar, Sampada Combinatorics 05C15 (Primary), 05A15, 06A07, 05C31 (Secondary) The bivariate chromatic polynomial $χ_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 $χ_G(x,y)$ as a sum of bivariate order polynomials (Beck-Farahmand-Karunaratne-Zuniga Ruiz 2020), and a combinatorial reciprocity theorem for $χ_G(x,y)$. |
| title | Bivariate Chromatic Polynomials of Mixed Graphs |
| topic | Combinatorics 05C15 (Primary), 05A15, 06A07, 05C31 (Secondary) |
| url | https://arxiv.org/abs/2111.09384 |