{
  "id": "2403.19573",
  "version": "v1",
  "published": "2024-03-28T16:56:58.000Z",
  "updated": "2024-03-28T16:56:58.000Z",
  "title": "$q$-Chromatic polynomials",
  "authors": [
    "Esme Bajo",
    "Matthias Beck",
    "Andrés R. Vindas-Meléndez"
  ],
  "comment": "16 pages, 1 figure",
  "categories": [
    "math.CO"
  ],
  "abstract": "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.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2024-03-28T16:56:58.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05A10",
      "05A15",
      "05C05",
      "05C30",
      "05C31",
      "05E05",
      "52B11",
      "52B12",
      "52B20"
    ],
    "keywords": [
      "chromatic polynomial",
      "chromatic symmetric function distinguishes trees",
      "ehrhart polynomials",
      "rational functions",
      "structural results"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 16,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}