# zbMATH — the first resource for mathematics

A symmetric function generalization of the chromatic polynomial of a graph. (English) Zbl 0831.05027
Author’s abstract: For a finite graph $$G$$ with $$d$$ vertices we define a homogeneous symmetric function $$X_G$$ of degree $$d$$ in the variables $$x_1, x_2, \ldots$$. If we set $$x_1 = \cdots = x_n = 1$$ and all other $$x_i = 0$$, then we obtain $$\chi_G (n)$$, the chromatic polynomial of $$G$$ evaluated at $$n$$. We consider the expansion of $$X_G$$ in terms of various symmetric function bases. The coefficients in these expansions are related to partitions of the vertices into stable subsets, the Möbius function of the lattice of contractions of $$G$$, and the structure of the acyclic orientations of $$G$$. The coefficients which arise when $$X_G$$ is expanded in terms of elementary symmetric functions are particularly interesting, and for certain graphs are related to the theory of Hecke algebras and Kazhdan-Lusztig polynomials.

##### MSC:
 05C15 Coloring of graphs and hypergraphs 05E05 Symmetric functions and generalizations
Full Text: