TOPICS
Search

Chromatic Quasisymmetric Function

The chromatic quasisymmetric function of a graph G with ordered vertex set [n]={1,...,n} is the generating function

X_G(x;q)=sum_(f)q^(asc_G(f))product_(i=1)^nx_(f(i)),

where f:[n]->N_(>0) ranges over proper colorings and asc_G(f) counts edges {i,j} with i<j and f(i)<f(j). A proper coloring assigns distinct colors to adjacent vertices. For a single edge on two vertices, X_G(x;q)=(1+q)e_2(x), where e_2 is the elementary symmetric polynomial. At q=1 the function is symmetric, and its specialization to m variables all equal to 1 is the chromatic polynomial evaluated at m. For natural unit interval graphs it is symmetric for general q and is the object in the Shareshian-Wachs conjecture.

See also

Chromatic Polynomial, Chromatic Symmetric Function, Elementary Symmetric Polynomial, Quasisymmetric Function, Shareshian-Wachs Conjecture

Explore with Wolfram|Alpha

References

Shareshian, J. and Wachs, M. L. "Chromatic Quasisymmetric Functions." Adv. Math. 295, 497-551, 2016. https://doi.org/10.1016/j.aim.2015.12.018.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 Quasisymmetric Function." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/ChromaticQuasisymmetricFunction.html

Subject classifications