The chromatic symmetric function is a symmetric function invariant of graphs studied in algebraic graph theory, a branch of mathematics.
It is the weight generating function for proper graph colorings, and was originally introduced by Richard Stanley as a generalization of the chromatic polynomial of a graph.
[1] For a finite graph
with vertex set
, a vertex coloring is a function
is a set of colors.
A vertex coloring is called proper if all adjacent vertices are assigned distinct colors (i.e.,
The chromatic symmetric function denoted
is defined to be the weight generating function of proper vertex colorings of
proper
be the monomial symmetric polynomial associated to
Consider the complete graph
Consider the path graph
: Altogether, the chromatic symmetric function of
There are a number of outstanding questions regarding the chromatic symmetric function which have received substantial attention in the literature surrounding them.
be the elementary symmetric function associated to
A partially ordered set
-free if it does not contain a subposet isomorphic to the direct sum of the
element chain and the
element chain.
The incomparability graph
is the graph with vertices given by the elements of
which includes an edge between two vertices if and only if their corresponding elements in
be the incomparability graph of a
[1] A weaker positivity result is known for the case of expansions into the basis of Schur functions.
Theorem (Gasharov) Let
be the incomparability graph of a
[3] In the proof of the theorem above, there is a combinatorial formula for the coefficients of the Schur expansion given in terms of
-tableaux which are a generalization of semistandard Young tableaux instead labelled with the elements of
There are a number of generalizations of the chromatic symmetric function: