This work shows the generating function for the q-chromatic polynomial in labeled graphs, indicating new properties with G-statistics.
Given a graph $G=(V,E)$ and a linear form λ∈ Z> 0V, Bajo et al. (2025) introduced the q-chromatic polynomial χG^λ(q,n) := ∑ q^∑v ∈ V λᵥ c(v) where the sum is over all proper colorings c: V → [n] := \ 1, 2, , n \; they showed that χG^λ(q,n) is a polynomial in [n]q := 1 + q + + qⁿ⁻¹ with coefficients in Z(q). For d ∈ Z>0 and the linear form given by (d,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, , 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, , 1), where certain coefficients of the numerator polynomial are palindromic polynomials in q.
No takes yet. Share an insight, caveat, or question.
Beck et al. (2025) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: