Improve this page

#Extended chromatic symmetric functions

L. Crew and S. Spirkl [CS19] introduce a vertex-weighted version of the chromatic symmetric functions. This has the advantage that it satisfies a deletion-contraction relation. Furthermore, this family of polynomials is also \(\omega \powerSum\)-positive. This can easily be seen from [AS19].

A. Ciliberti extends chromatic symmetric homology to vertex-weighted graphs [Cil24]. This categorifies the Crew–Spirkl invariant and gives a deletion–contraction long exact sequence lifting the deletion–contraction relation for vertex-weighted chromatic symmetric functions.

In [CS21], the authors examine a new basis, the complete multipartite basis, whose elements are chromatic symmetric functions of complete multipartite graphs. They give combinatorial interpretations for the change-of-basis coefficients with the monomial basis, and for chromatic and Tutte symmetric functions expanded in this basis. More explicitly, if \(G_\lambda\) is the complete multipartite graph with stable-set sizes \(\lambda,\) then \[r_\lambda \coloneqq X_{G_\lambda}.\] For each \(d,\) the functions \(\{r_\lambda:\lambda\vdash d\}\) form a basis for the degree-\(d\) part of the ring of symmetric functions [Sec. 3, CS21].

Example (Chromatic bases in degrees 2 and 3).

In degree \(2,\) the graph \(G_{(2)}\) is edgeless and \(G_{(1,1)}\) is the complete graph \(K_2.\) Thus \[r_{(2)}=\monomial_2+2\monomial_{11}, \qquad r_{(1,1)}=2\monomial_{11}.\] In degree \(3,\) direct enumeration of proper colorings gives \[\begin{aligned} r_{(3)} &= \monomial_3+3\monomial_{21}+6\monomial_{111},\\ r_{(2,1)} &= \monomial_{21}+6\monomial_{111},\\ r_{(1,1,1)} &= 6\monomial_{111}. \end{aligned}\] These triangular expansions are the first instances of the fact that the \(r_\lambda\) form a basis.

The deletion-contraction relation does not extend to the \(q\)-weighted version with ascents.

Y. Sato introduces a common generalization of vertex-weighted chromatic symmetric functions and chromatic functions coming from universal graph series [Sat24]. This gives complete invariants for finite vertex-weighted graphs when the target graph, or target graph series, is universal, and it includes a power-sum expansion for the complete-graph series.

In [AWW21], the authors study weighted paths with equal extended chromatic symmetric functions.

In [AWW21], the authors consider a Tutte-symmetric extension of the vertex-weighted chromatic symmetric functions. This generalizes both Tutte symmetric functions and the chromatic symmetric functions. They provide a spanning-tree formula for these, which then provides a new spanning-tree formula for the chromatic symmetric functions.

F. Aliniaeifard, S. X. Li, and S. v. Willigenburg introduce generalized chromatic functions of edge-coloured digraphs [ALW24]. This framework contains Stanley’s chromatic symmetric functions, extended chromatic symmetric functions, chromatic quasisymmetric functions, and \(P\)-partition generating functions as special cases. It also realizes many standard symmetric and quasisymmetric bases as generalized chromatic functions and gives product and coproduct formulas.

J. L. Martin and M. B. Trist introduce chromatic MacMahon symmetric functions for vertex-weighted graphs [MT25]. These take values in MacMahon symmetric functions on two alphabets and refine weighted chromatic information by recording both cardinalities and weights of vertex subsets. For trees, the invariant determines the generating function of vertex subsets by cardinality, weight, and the number of internal and external edges, extending the unweighted subset-reconstruction results for chromatic symmetric functions.

N. M. Eagles, A. Foley, A. Huang, E. Karangozishvili, and A. Yu introduce \(H\)-chromatic symmetric functions [EFHK+22]. Here a fixed graph \(H\) restricts the colorings of a graph \(G.\) This gives new graph invariants, new uniqueness questions, and realizations of the monomial, power-sum, and elementary bases as \(H\)-chromatic symmetric functions of complete multipartite graphs.

S. Y. Lin and L. Pierson study distinguishability and linear independence phenomena for \(H\)-chromatic symmetric functions [LP25]. For the self-chromatic functions \(X_G^G,\) they give evidence and structural results related to tree distinguishability, prove results for complete bipartite targets, and construct bases of \(\Lambda^n\) from \(H\)-chromatic symmetric functions for fixed non-complete target graphs.

Problem

Is there a chromatic quasisymmetric analogue of the spanning-tree formula of [AWW21]?

Bibliography

  1. [AS19]Per Alexandersson and Robin Sulzgruber. P-partitions and p-positivity. International Mathematics Research Notices, 2021(14):10848–10907, July 2019.
    .bib
    @article{AlexanderssonSulzgruber2019,
  title = {{P}-Partitions and {p}-Positivity},
  volume = {2021},
  ISSN = {1687-0247},
  url = {http://dx.doi.org/10.1093/imrn/rnz130},
  DOI = {10.1093/imrn/rnz130},
  number = {14},
  journal = {International Mathematics Research Notices},
  publisher = {Oxford University Press (OUP)},
  author = {Alexandersson,  Per and Sulzgruber,  Robin},
  year = {2019},
  month = jul,
  pages = {10848–10907}
}
  2. [ALW24]Farid Aliniaeifard, Shu Xiao Li and Stephanie Willigenburg. Generalized Chromatic Functions. International Mathematics Research Notices, 2024(5):4456–4500, 2024.
    .bib
    @article{AliniaeifardLiWilligenburg2024,
  author = {Aliniaeifard, Farid and Li, Shu Xiao and van Willigenburg, Stephanie},
  title = {Generalized {C}hromatic {F}unctions},
  year = {2024},
  journal = {International Mathematics Research Notices},
  volume = {2024},
  number = {5},
  pages = {4456--4500},
  publisher = {Oxford University Press (OUP)},
  doi = {10.1093/imrn/rnad149},
  url = {http://dx.doi.org/10.1093/imrn/rnad149},
  issn = {1687-0247}
}
  3. [AWW21]Farid Aliniaeifard, Victor Wang and Stephanie Willigenburg. Extended chromatic symmetric functions and equality of ribbon Schur functions. Advances in Applied Mathematics, 128:102189, July 2021.
    .bib
    @article{AliniaeifardWangvanWilligenburg2021,
  title = {Extended chromatic symmetric functions and equality of ribbon {S}chur functions},
  volume = {128},
  ISSN = {0196-8858},
  url = {http://dx.doi.org/10.1016/j.aam.2021.102189},
  DOI = {10.1016/j.aam.2021.102189},
  journal = {Advances in Applied Mathematics},
  publisher = {Elsevier BV},
  author = {Aliniaeifard,  Farid and Wang,  Victor and van Willigenburg,  Stephanie},
  year = {2021},
  month = jul,
  pages = {102189}
}
  4. [Cil24]Azzurra Ciliberti. A deletion–contraction long exact sequence for chromatic symmetric homology. European Journal of Combinatorics, 115:103788, 2024.
    .bib
    @article{Ciliberti2024,
  author = {Ciliberti, Azzurra},
  title = {A deletion--contraction long exact sequence for chromatic symmetric
    homology},
  year = {2024},
  journal = {European Journal of Combinatorics},
  volume = {115},
  pages = {103788},
  publisher = {Elsevier BV},
  doi = {10.1016/j.ejc.2023.103788},
  url = {https://doi.org/10.1016/j.ejc.2023.103788},
  eprint = {2211.00699}
}
  5. [CS19]Logan Crew and Sophie Spirkl. A deletion-contraction relation for the chromatic symmetric function. arXiv:1910.11859, 2019.
    .bib
    @article{CrewSpirkl2019x,
Author = {Logan Crew and Sophie Spirkl},
Title = {A Deletion-Contraction Relation for the Chromatic Symmetric Function},
Year = {2019},
Eprint = {1910.11859},
  url = {https://arxiv.org/abs/1910.11859},
journal = {arXiv e-prints}
}
  6. [CS21]Logan Crew and Sophie Spirkl. A Complete Multipartite Basis for the Chromatic Symmetric Function. SIAM Journal on Discrete Mathematics, 35(4):2647–2661, 2021.
    .bib
    @article{CrewSpirkl2020x,
  author = {Crew, Logan and Spirkl, Sophie},
  title = {A {C}omplete {M}ultipartite {B}asis for the {C}hromatic
    {S}ymmetric {F}unction},
  year = {2021},
  journal = {SIAM Journal on Discrete Mathematics},
  volume = {35},
  number = {4},
  pages = {2647--2661},
  publisher = {Society for Industrial \& Applied Mathematics (SIAM)},
  doi = {10.1137/20m1380314},
  url = {http://dx.doi.org/10.1137/20M1380314},
  issn = {1095-7146}
}
  7. [EFHK+22]Nancy Mae Eagles, Angele M. Foley, Alice Huang, Elene Karangozishvili and Annan Yu. ${H}$-Chromatic Symmetric Functions. The Electronic Journal of Combinatorics, 29(1), 2022.
    .bib
    @article{EaglesFoleyHuangKarangozishviliYu2022,
  author = {Eagles, Nancy Mae and Foley, Angele M. and Huang, Alice and Karangozishvili, Elene and Yu, Annan},
  title = {${H}$-{C}hromatic {S}ymmetric {F}unctions},
  year = {2022},
  journal = {The Electronic Journal of Combinatorics},
  volume = {29},
  number = {1},
  publisher = {The Electronic Journal of Combinatorics},
  doi = {10.37236/10011},
  url = {http://dx.doi.org/10.37236/10011},
  issn = {1077-8926}
}
  8. [LP25]Shao Yuan Lin and Laura Pierson. Distinguishability and linear independence for ${H}$-chromatic symmetric functions. arXiv:2511.08665, 2025.
    .bib
    @article{LinPierson2025HChromaticx,
  author = {Shao Yuan Lin and Laura Pierson},
  title = {Distinguishability and linear independence for ${H}$-chromatic
    symmetric functions},
  year = {2025},
  eprint = {2511.08665},
  url = {https://arxiv.org/abs/2511.08665},
  journal = {arXiv e-prints}
}
  9. [MT25]Jeremy L. Martin and May B. Trist. Chromatic MacMahon symmetric functions of graphs. arXiv:2508.00157, 2025.
    .bib
    @article{MartinTrist2025x,
  author = {Jeremy L. Martin and May B. Trist},
  title = {Chromatic {M}ac{M}ahon symmetric functions of graphs},
  year = {2025},
  eprint = {2508.00157},
  url = {https://arxiv.org/abs/2508.00157},
  journal = {arXiv e-prints}
}
  10. [Sat24]Yosuke Sato. Universal graph series and vertex-weighted version of chromatic symmetric function. arXiv:2410.22813, 2024.
    .bib
    @article{Sato2024x,
  author = {Yosuke Sato},
  title = {Universal graph series and vertex-weighted version of chromatic symmetric function},
  year = {2024},
  eprint = {2410.22813},
  url = {https://arxiv.org/abs/2410.22813},
  journal = {arXiv e-prints}
}

I use cookies to detect website issues and track search terms.