Homogeneous sets in graphs and a chromatic multisymmetric function (Q6564066)

In this article, the authors introduce a new multisymmetric function that arises as an extension of the well-studied chromatic symmetric function. The authors introduce \(k\)-vertex-labelled graphs, defined by labelling the vertices of a graph \(G\) with one of \(k\) labels, which induces a partition of its vertex set \(V(G)\) into \(k\) parts. This new \(k\)-multisymmetric function is defined for graphs that can be associated with such a partition. This multisymmetric function maintains some of the essential properties and basis expansions of the chromatic symmetric function. They also provide a method for deriving new linear relationships for the chromatic symmetric function from previous ones by going through the new \(k\)-multisymmetric function. A homogeneous set of \(G\) are those sets \(S\subseteq V(G)\) such that each vertex \(V(G)\setminus S\) is either adjacent to all of \(S\) or is nonadjacent to all of \(S\). The authors show how to use these homogeneous sets to relate the chromatic symmetric function of a graph to those of simpler graphs. In essence, by developing a multisymmetric function that captures the chromatic aspects of graphs containing homogeneous sets, the study enhances the understanding of combinatorial structures and offers new tools for exploring graph invariants. The results contribute to ongoing discussions in graph theory, particularly regarding the interplay between homogeneity and coloring techniques.