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.

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