1. $q$-Chromatic polynomials
- Author
-
Bajo, Esme, Beck, Matthias, and Vindas-Meléndez, Andrés R.
- Subjects
Mathematics - Combinatorics ,05A10, 05A15, 05C05, 05C30, 05C31, 05E05, 52B11, 52B12, 52B20 - Abstract
We introduce and study a $q$-version of the chromatic polynomial of a given graph $G=(V,E)$, namely, \[ \chi_G^\lambda(q,n) \ := \sum_{\substack{\text{proper colorings}\\ c\,:\,V\to[n]}} q^{ \sum_{ v \in V } \lambda_v c(v) }, \] where $\lambda \in \mathbb{Z}^V$ is a fixed linear form. Via work of Chapoton (2016) on $q$-Ehrhart polynomials, $\chi_G^\lambda(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 $\chi_G^\lambda(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., Comment: 16 pages, 1 figure
- Published
- 2024