q-Chromatic polynomials
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
- Generating functions of $q$-chromatic polynomials
- The chromatic symmetric function in the star-basis
- Generalized Whitney formulas for broken circuits in ambigraphs and matroids
Related papers
- Three-ends Furstenberg estimates and approximate rectangles
- Multicolor Ramsey numbers of ordered matchings
- Exponential random graph models with soft clique constraints
- A Full-Sequence Quantitative Gap Between the Chromatic and Cochromatic Numbers of a Random Graph
- Ehrhart positivity for paving positroids
- Nonlinear lower-tail large deviations at criticality