Vertex-Weighted Generalizations Of Chromatic Symmetric Functions

Defined by Richard Stanley in the early 1990s, the chromatic symmetric func- tion X G of a graph G enumerates for each integer partition λ of |V (G)| the number of proper colorings of G that partition V (G) into stable sets of sizes equal to the parts of λ. Thus, X G is a refinement of the well-known chromatic polynomial χ G , and its coefficients in different symmetric function bases provide further informa- tion on the structure of G than χ G . However, X G loses some of the utility of χ G because it fails to admit a natural edge deletion-contraction relation. To address this shortcoming we introduce vertex-weighted graphs (G, w) consisting of a graph G and a weight function w : V (G) → N. Then X G extends in a natural way to a new function X (G,w) on vertex-weighted graphs. We demonstrate that X (G,w) satisfies a deletion-contraction relation akin to that of the chromatic polynomial, and use this relation to both derive new properties of the chromatic symmetric function and prove previously known properties in an original way. In the case of prior results, the new proofs are typically simpler and more intuitive than the original proofs, and are more closely related to analogous proofs of properties of the chromatic polyno- mial. We then demonstrate how the deletion-contraction relation can be used as a new tool to research open questions involving X G . We also explore a similar ex- tension of the bad-coloring chromatic symmetric function XB G to vertex-weighted graphs, and we consider applications of these new functions to graph isomorphism and symmetric function bases.