$q$-Chromatic polynomials
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908854886858752 |
|---|---|
| author | Bajo, Esme Beck, Matthias Vindas-Meléndez, Andrés R. |
| author_facet | Bajo, Esme Beck, Matthias Vindas-Meléndez, Andrés R. |
| contents | We study a $q$-version of the chromatic polynomial of a given graph $G=(V,E)$, namely, \[ χ_G^λ(q,n) \ := \sum_{\substack{\text{proper colorings}\\ c\,:\,V\to[n]}} q^{ \sum_{ v \in V } λ_v c(v) }, \] where $λ\in \mathbb{Z}_{>0}^V$ is a fixed linear form. Via work of Chapoton (2016) on $q$-Ehrhart polynomials, $χ_G^λ(q,n)$ turns out to be a polynomial in the $q$-integer $[n]_q$, with coefficients that are rational functions in $q$. Additionally, we prove structural results for $χ_G^λ(q,n)$ and exhibit connections to neighboring concepts, e.g., chromatic symmetric functions and the arithmetic of order polytopes. We offer a strengthened version of Stanley's conjecture that the chromatic symmetric function distinguishes trees, which leads to an analogue of $P$-partitions for graphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2403_19573 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | $q$-Chromatic polynomials Bajo, Esme Beck, Matthias Vindas-Meléndez, Andrés R. Combinatorics 05A10, 05A15, 05C05, 05C30, 05C31, 05E05, 52B11, 52B12, 52B20 We study a $q$-version of the chromatic polynomial of a given graph $G=(V,E)$, namely, \[ χ_G^λ(q,n) \ := \sum_{\substack{\text{proper colorings}\\ c\,:\,V\to[n]}} q^{ \sum_{ v \in V } λ_v c(v) }, \] where $λ\in \mathbb{Z}_{>0}^V$ is a fixed linear form. Via work of Chapoton (2016) on $q$-Ehrhart polynomials, $χ_G^λ(q,n)$ turns out to be a polynomial in the $q$-integer $[n]_q$, with coefficients that are rational functions in $q$. Additionally, we prove structural results for $χ_G^λ(q,n)$ and exhibit connections to neighboring concepts, e.g., chromatic symmetric functions and the arithmetic of order polytopes. We offer a strengthened version of Stanley's conjecture that the chromatic symmetric function distinguishes trees, which leads to an analogue of $P$-partitions for graphs. |
| title | $q$-Chromatic polynomials |
| topic | Combinatorics 05A10, 05A15, 05C05, 05C30, 05C31, 05E05, 52B11, 52B12, 52B20 |
| url | https://arxiv.org/abs/2403.19573 |