q-Chromatic polynomials

arXiv:2403.19573 · math.CO · Submitted 2024-03-28 · Read on arXiv

math.CO

Submitted: 2024-03-28

Updated: 2026-10-26

Comments: 20 pages, 2 tables

License: http://creativecommons.org/licenses/by/4.0/

The gist: We study a q-version of the chromatic polynomial of a given graph G=(V,E), namely, χ G λ(q,n):= sum q sum v in V λ v c(v), where λ in Z>0 V is a fixed linear form.

Terminology

Abstract

We study a q-version of the chromatic polynomial of a given graph G=(V,E), namely, χ G λ(q,n):= sum q sum v in V λ v c(v), where λ in Z>0 V is a fixed linear form. Via work of Chapoton (2016) on q-Ehrhart polynomials, χ G λ(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 χ G λ(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.

Sources

Related papers