Homogeneous Sets in Graphs and a Chromatic Multisymmetric Function

Publication date 28 September 2022

Abstract: In this paper, we extend the chromatic symmetric function

X

to a chromatic

k

-multisymmetric function

X_{k}

, defined for graphs equipped with a partition of their vertex set into

k

parts. We demonstrate that this new function retains the basic properties and basis expansions of

X

, and we give a method for systematically deriving new linear relationships for

X

from previous ones by passing them through

X_{k}

. In particular, we show how to take advantage of homogeneous sets of

G

(those

S s u b s e t e q V (G)

such that each vertex of

is either adjacent to all of

S

or is nonadjacent to all of

S

) to relate the chromatic symmetric function of

G

to those of simpler graphs. Furthermore, we show how extending this idea to homogeneous pairs

S_{1} s q c u p S_{2} s u b s e t e q V (G)

generalizes the process used by Guay-Paquet to reduce the Stanley-Stembridge conjecture to unit interval graphs.

This page was built for publication: Homogeneous Sets in Graphs and a Chromatic Multisymmetric Function