Generating functions of $q$-chromatic polynomials
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916973248512000 |
|---|---|
| author | Beck, Matthias Braun, Benjamin Cornejo, Alvaro |
| author_facet | Beck, Matthias Braun, Benjamin Cornejo, Alvaro |
| contents | Given a graph $G=(V,E)$ and a linear form $λ\in \mathbb{Z}_{ > 0 }^V$, Bajo et al. (2025) introduced the $q$-chromatic polynomial $χ_G^λ(q,n) := \sum q^{\sum_{v \in V} λ_v c(v)}$ where the sum is over all proper colorings $c: V \to [n] := \{ 1, 2, \dots, n \}$; they showed that $χ_G^λ(q,n)$ is a polynomial in $[n]_q := 1 + q + \dots + q^{ n-1 } $ with coefficients in $\mathbb{Z}(q)$. For $d \in \mathbb{Z}_{>0}$ and the linear form given by $(d,d^2,\ldots,d^d)$, we show that the $q$-chromatic polynomial distinguishes labeled graphs with vertex set $[d]$. Using permutation statistics introduced by Chung--Graham (1995), called $G$-statistics, and polyhedral geometry, we give the multivariate integer point transform for the region of proper colorings of a given graph $G$. This integer point transform allows us to find the generating function for the $q$-chromatic polynomial with respect to any linear form. We further specialize these results to the linear form $(1, 1, \dots, 1)$, which allows us to write the $q$-chromatic polynomial in the $q$-binomial basis, clarifying expressions found by Bajo et al. Moreover, we show that $G$-statistics are compatible with the theory of order polytopes used by Bajo et al. and Chow (1999). This yields further properties for the generating function of $q$-chromatic polynomial with linear form $(1, 1, \dots, 1)$, where certain coefficients of the numerator polynomial are palindromic polynomials in $q$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_22946 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Generating functions of $q$-chromatic polynomials Beck, Matthias Braun, Benjamin Cornejo, Alvaro Combinatorics 05A15, 52B20, 05C31, 05E05 Given a graph $G=(V,E)$ and a linear form $λ\in \mathbb{Z}_{ > 0 }^V$, Bajo et al. (2025) introduced the $q$-chromatic polynomial $χ_G^λ(q,n) := \sum q^{\sum_{v \in V} λ_v c(v)}$ where the sum is over all proper colorings $c: V \to [n] := \{ 1, 2, \dots, n \}$; they showed that $χ_G^λ(q,n)$ is a polynomial in $[n]_q := 1 + q + \dots + q^{ n-1 } $ with coefficients in $\mathbb{Z}(q)$. For $d \in \mathbb{Z}_{>0}$ and the linear form given by $(d,d^2,\ldots,d^d)$, we show that the $q$-chromatic polynomial distinguishes labeled graphs with vertex set $[d]$. Using permutation statistics introduced by Chung--Graham (1995), called $G$-statistics, and polyhedral geometry, we give the multivariate integer point transform for the region of proper colorings of a given graph $G$. This integer point transform allows us to find the generating function for the $q$-chromatic polynomial with respect to any linear form. We further specialize these results to the linear form $(1, 1, \dots, 1)$, which allows us to write the $q$-chromatic polynomial in the $q$-binomial basis, clarifying expressions found by Bajo et al. Moreover, we show that $G$-statistics are compatible with the theory of order polytopes used by Bajo et al. and Chow (1999). This yields further properties for the generating function of $q$-chromatic polynomial with linear form $(1, 1, \dots, 1)$, where certain coefficients of the numerator polynomial are palindromic polynomials in $q$. |
| title | Generating functions of $q$-chromatic polynomials |
| topic | Combinatorics 05A15, 52B20, 05C31, 05E05 |
| url | https://arxiv.org/abs/2509.22946 |