A Noncommutative Chromatic Symmetric Function

Original · EN

Stanley associated with a graph G a symmetric function XG which reduces to G's chromatic polynomial under a certain specialization of variables. He then proved various theorems generalizing results about the chromatic polynomial, as well as new ones that cannot be interpreted at that level. Unfortunately, XG does not satisfy a Deletion-Contraction Law which makes it difficult to apply induction. We introduce a symmetric function in noncommuting variables which does have such a law and specializes to XG when the variables are allowed to commute. This permits us to further generalize some of Stanley's theorems and prove them in a uniform and straightforward manner. Furthermore, we make some progress on the (3+1)-free Conjecture of Stanley and Stembridge.