EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Generating functions of q -chromatic polynomials

Matthias Beck, Benjamin Braun, Alvaro Cornejo

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).

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →