q-Chromatic Polynomials

Series: Algebra Seminar
Time: Monday, April 1, 2024 - 1:00pm for 1 hour (actually 50 minutes)
Location: Skiles 005
Speaker: Andrés R. Vindas Meléndez – University of California, Berkeley
Organizer: Changxin Ding

We introduce and study a

$q$ -version of the chromatic polynomial of a given graph

$G=(V,E)$ , namely,

$\chi_G^\lambda(q,n) \ := \sum_{\substack{\text{proper colorings}\\ c\,:\,V\to[n]}} q^{ \sum_{ v \in V } \lambda_v c(v) },$ where

$\lambda \in \mathbb{Z}^V$ is a fixed linear form.
Via work of Chapoton (2016) on

$q$ -Ehrhart polynomials,

$\chi_G^\lambda(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

$\chi_G^\lambda(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.

This is joint work with Esme Bajo and Matthias Beck.

Georgia Institute of Technology College of Sciences

Search form

q-Chromatic Polynomials