TOPICS
Search

Chromatic Symmetric Function

The chromatic symmetric function of a finite simple graph G is the symmetric function

X_G(x_1,x_2,...)=sum_(kappa)product_(v in V(G))x_(kappa(v)),

where the sum ranges over proper colorings kappa by positive integers (Stanley 1995). Setting x_1=...=x_m=1 and all remaining variables to zero gives the chromatic polynomial of G evaluated at m.

Bingham et al. (2026) refined this function by recording the number of colors used:

Z_G(x_1,x_2,...;t)=sum_(kappa)t^(|kappa(V(G))|)product_(v in V(G))x_(kappa(v)).

Thus Z_G(x_1,x_2,...;1)=X_G(x_1,x_2,...). They proved that the specialization Z_G(1,q,q^2,0,0,...;t) determines G up to isomorphism within each of two classes of caterpillar graphs. One consists of those whose nonleaf vertices form a three-vertex path graph. The other consists of elongated bistars, obtained by joining the centers of two star graphs, each having at least one leaf, by a path graph. Their proof supplies reconstruction algorithms. Bingham et al. (2026) used AI-generated code to check related reconstruction conjectures at larger orders.

See also

Caterpillar Graph, Chromatic Polynomial, Chromatic Quasisymmetric Function, Symmetric Function

Explore with Wolfram|Alpha

References

Bingham, A.; Celano, K.; Commins, P.; Orellana, R.; Pan, J.; and Simone, M. C. "Principal Specializations of the t-Chromatic Symmetric Function." 22 Oct 2026. https://arxiv.org/abs/2610.31785.Stanley, R. P. "A Symmetric Function Generalization of the Chromatic Polynomial of a Graph." Adv. Math. 111, 166-194, 1995. https://doi.org/10.1006/aima.1995.1020.

Cite this as:

Weisstein, Eric W. "Chromatic Symmetric Function." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/ChromaticSymmetricFunction.html

Subject classifications