A MacMahon symmetric function is an invariant of the diagonal action of the symmetric group on power series in multiple alphabets of variables. We introduce an analogue of the chromatic symmetric function for vertex-weighted graphs, taking values in the MacMahon symmetric functions on two sets of variables, recording information about both cardinalities and weights of vertex sets. We prove that the chromatic symmetric MacMahon function of a tree determines the generating function for its vertex subsets by cardinality, weight, and the numbers of internal and external edges. This result generalizes the one for the unweighted case, first conjectured by Crew and proved independently by Aliste-Prieto–Martin–Wagner–Zamora and Liu–Tang.
Revised:
Accepted:
Published online:
Keywords: Chromatic symmetric function, generalized degree sequence, weighted graph, MacMahon symmetric function, Crew’s conjecture
Martin, Jeremy L. 1 ; Trist, May B. 1
CC-BY 4.0
Martin, Jeremy L.; Trist, May B. Chromatic MacMahon symmetric functions of graphs. Algebraic Combinatorics, Volume 9 (2026) no. 3, pp. 597-610. doi: 10.5802/alco.496
@article{ALCO_2026__9_3_597_0,
author = {Martin, Jeremy L. and Trist, May B.},
title = {Chromatic {MacMahon} symmetric functions of graphs},
journal = {Algebraic Combinatorics},
pages = {597--610},
year = {2026},
publisher = {The Combinatorics Consortium},
volume = {9},
number = {3},
doi = {10.5802/alco.496},
language = {en},
url = {https://alco.centre-mersenne.org/articles/10.5802/alco.496/}
}
TY - JOUR AU - Martin, Jeremy L. AU - Trist, May B. TI - Chromatic MacMahon symmetric functions of graphs JO - Algebraic Combinatorics PY - 2026 SP - 597 EP - 610 VL - 9 IS - 3 PB - The Combinatorics Consortium UR - https://alco.centre-mersenne.org/articles/10.5802/alco.496/ DO - 10.5802/alco.496 LA - en ID - ALCO_2026__9_3_597_0 ER -
%0 Journal Article %A Martin, Jeremy L. %A Trist, May B. %T Chromatic MacMahon symmetric functions of graphs %J Algebraic Combinatorics %D 2026 %P 597-610 %V 9 %N 3 %I The Combinatorics Consortium %U https://alco.centre-mersenne.org/articles/10.5802/alco.496/ %R 10.5802/alco.496 %G en %F ALCO_2026__9_3_597_0
[1] Marked graphs and the chromatic symmetric function, SIAM J. Discrete Math., Volume 37 (2023) no. 3, pp. 1881-1919 | DOI | MR | Zbl
[2] Chromatic symmetric functions and polynomial invariants of trees, Bull. Lond. Math. Soc., Volume 56 (2024) no. 11, pp. 3452-3476 | MR | Zbl | DOI
[3] Vassiliev knot invariants. III. Forest algebra and weighted graphs, Singularities and bifurcations (Adv. Soviet Math.), Volume 21, Amer. Math. Soc., Providence, RI, 1994, pp. 135-145 | MR | Zbl | DOI
[4] Chromatic bases for symmetric functions, Electron. J. Combin., Volume 23 (2016) no. 1, Paper no. 1.15, 7 pages | Zbl | DOI | MR
[5] Vertex-weighted Generalizations of Chromatic Symmetric Functions, Ph. D. Thesis, University of Pennsylvania (2020)
[6] A note on distinguishing trees with the chromatic symmetric function, Discrete Math., Volume 345 (2022) no. 2, Paper no. 112682, 4 pages | DOI | MR | Zbl
[7] A deletion-contraction relation for the chromatic symmetric function, European J. Combin., Volume 89 (2020), Paper no. 103143, 20 pages | DOI | MR | Zbl
[8] Graph Theory, Graduate Texts in Mathematics, 173, Springer, Berlin, 2018, xviii+428 pages | MR
[9] The chromatic symmetric function in the star-basis, Discrete Math., Volume 349 (2026) no. 2, Paper no. 114691, 28 pages | DOI | MR | Zbl
[10] Hopf Algebras in Combinatorics, 2014 | arXiv | Zbl
[11] The primitives and antipode in the Hopf algebra of symmetric functions in noncommuting variables, Adv. in Appl. Math., Volume 47 (2011) no. 3, pp. 536-544 | DOI | MR | Zbl
[12] Generalized degree polynomials of trees, 2024 (forthcoming, Trans. Amer. Math. Soc.) | arXiv | Zbl
[13] Isomorphism of weighted trees and Stanley’s isomorphism conjecture for caterpillars, Ann. Inst. Henri Poincaré D, Volume 6 (2019) no. 3, pp. 357-384 | DOI | MR | Numdam | Zbl
[14] Combinatory analysis, Chelsea Publishing Co., New York, 1960, xix+302+xix+340 pages | MR | Zbl
[15] On distinguishing trees by their chromatic symmetric functions, J. Combin. Theory Ser. A, Volume 115 (2008) no. 2, pp. 237-253 | DOI | MR | Zbl
[16] A weighted graph polynomial from chromatic invariants of knots, Ann. Inst. Fourier (Grenoble), Volume 49 (1999) no. 3, pp. 1057-1087 | DOI | MR | Zbl | Numdam
[17] MacMahon symmetric functions, the partition lattice, and Young subgroups, J. Combin. Theory Ser. A, Volume 96 (2001) no. 2, pp. 326-340 | DOI | MR | Zbl
[18] A combinatorial overview of the Hopf algebra of MacMahon symmetric functions, Ann. Comb., Volume 6 (2002) no. 2, pp. 195-207 | DOI | MR | Zbl
[19] Characterizing Graphs with Equal Chromatic Functions, undergraduate thesis, Dartmouth College (2008)
[20] A symmetric function generalization of the chromatic polynomial of a graph, Adv. Math., Volume 111 (1995) no. 1, pp. 166-194 | Zbl | DOI | MR
[21] Enumerative combinatorics. Vol. 2, Cambridge Studies in Advanced Mathematics, 62, Cambridge U. Press, Cambridge, 1999, xii+581 pages | Zbl | DOI | MR
[22] A class of trees determined by their chromatic symmetric functions, Discrete Math., Volume 347 (2024) no. 9, Paper no. 114096, 11 pages | Zbl | DOI | MR
Cited by Sources: