Let G be a combinatorial graph with vertex set V and edge set E. A ``proper coloring'' of G is a function c from V to {1,2,...n} such that if uv is an edge then c(u) does not equal c(v). This is the same restriction as in the famous Four Color Theorem. In 1912, G. D. Birkhoff showed that the number of proper colorings is a polynomial in n, called the chromatic polynomial P(G,n), which has many wonderful properties. More recently, Stanley showed that one can associate with G a symmetric function X(G,x) which reduces to P(G,n) under specialization of the variable set x. But P(G,n) satisfies a deletion-contraction law which is useful for inductive proofs of its properties, while X(G,x) does not. We will show how one can derive such a law using symmetric functions in noncommuting variables and give applications.
I will not assume any background about graph coloring or symmetric functions.
This is joint work with David Gebhard.