Homogeneous sets in graphs and a chromatic multisymmetric function
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.
- \(H\)-chromatic symmetric functions
- A symmetric function generalization of the chromatic polynomial of a graph
- A deletion-contraction relation for the chromatic symmetric function
- A quasisymmetric function generalization of the chromatic symmetric function
- A vertex-weighted Tutte symmetric function, and constructing graphs with equal chromatic symmetric function
- A combinatorial expansion of vertical-strip LLT polynomials in the basis of elementary symmetric functions
- A combinatorial formula for the Schur coefficients of chromatic symmetric functions
- A deletion-contraction relation for the chromatic symmetric function
- A new formula for Stanley's chromatic symmetric function for unit interval graphs and E-positivity for triangular ladder graphs
- A symmetric function generalization of the chromatic polynomial of a graph
- Chromatic symmetric functions from the modular law
- Chromatic symmetric functions of Dyck paths and \(q\)-rook theory
- Chromatic symmetric functions via the group algebra of \(S_n\)
- Classes of graphs with \(e\)-positive chromatic symmetric function
- Graphs with equal chromatic symmetric functions
- scientific article; zbMATH DE number 1268810 (Why is no real title available?)
- scientific article; zbMATH DE number 1181673 (Why is no real title available?)
- Lollipop and lariat symmetric functions
- Modular relations of the Tutte symmetric function
- Multisymmetric functions
- On $e$-Positivity and $e$-Unimodality of Chromatic Quasi-symmetric Functions
- On an algorithm for comparing the chromatic symmetric functions of trees
- On trees with the same restricted \(U\)-polynomial and the Prouhet-Tarry-Escott problem
- Positivity of chromatic symmetric functions associated with Hessenberg functions of bounce number 3
- Schur and \(e\)-positivity of trees and cut vertices
- Strongly perfect claw‐free graphs—A short proof
- Structure and enumeration of \((3+1)\)-free posets
- The kernel of chromatic quasisymmetric functions on graphs and hypergraphic polytopes
- The ring of multisymmetric functions.
- The strong perfect graph theorem
This page was built for publication: Homogeneous sets in graphs and a chromatic multisymmetric function
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6564066)
