Generating functions of q -chromatic polynomials
International Mathematics Research Notices · 25.11.2026 · 2026 (22)
DOI: 10.1093/imrn/rnag241 ↗Kurz gefasst
Fachartikel in der Zeitschrift International Mathematics Research Notices, online erschienen am 12.11.2026. Verfasst von Matthias Beck und 2 weiteren Autor:innen. Die Arbeit nennt 12 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).
Abstract (Originalsprache)
Given a graph $G=(V,E)$ and a linear form $\lambda \in \mathbb{Z}_{> 0 }^{V}$, Bajo et al. (2025) introduced the $q$-chromatic polynomial $\chi _{G}^\lambda (q,n):= \sum q^{\sum _{v \in V} \lambda _{v} c(v)}$ where the sum is over all proper colorings $c: V \to [n]:= \{ 1, 2, \dots , n \}$; they showed that $\chi _{G}^\lambda (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 , 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 , where certain coefficients of the numerator polynomial are palindromic polynomials in $q$.
Zitieren
APA
Beck, M., Braun, B., & Cornejo, A. (2026). Generating functions of q -chromatic polynomials. International Mathematics Research Notices, 2026(22). https://doi.org/10.1093/imrn/rnag241
Vancouver
Beck M, Braun B, Cornejo A. Generating functions of q -chromatic polynomials. International Mathematics Research Notices. 2026;2026(22). doi:10.1093/imrn/rnag241
BibTeX
@article{Beck2026,
author = {Beck, Matthias and Braun, Benjamin and Cornejo, Alvaro},
title = {Generating functions of q -chromatic polynomials},
journal = {International Mathematics Research Notices},
year = {2026},
volume = {2026},
number = {22},
doi = {10.1093/imrn/rnag241}
}
EUVIMED