Marked Graphs and the Chromatic Symmetric Function

DOI10.1137/22M148046XMaRDI QIDQ6046819zbMATH OpenFDO

Authors

Publication date 6 September 2023

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2202.11787

zbMATH Keywords

chromatic basischromatic symmetric functiontrees

Mathematics Subject Classification ID

Trees (05C05) Graph polynomials (05C31) Symmetric functions and generalizations (05E05)

Abstract: The main result of this paper is the introduction of marked graphs and the marked graph polynomials ($M$-polynomial) associated with them. These polynomials can be defined via a deletion-contraction operation. These polynomials are a generalization of the $W$-polynomial introduced by Noble and Welsh and a specialization of the $mathbfV$-polynomial introduced by Ellis-Monaghan and Moffatt. In addition, we describe an important specialization of the $M$-polynomial which we call the $D$-polynomial. Furthermore, we give an efficient algorithm for computing the chromatic symmetric function of a graph in the emph{star-basis} of symmetric functions. As an application of these tools, we prove that proper trees of diameter at most 5 can be reconstructed from its chromatic symmetric function.

Recommendations

• Chromatic symmetric functions and \(H\)-free graphs
• Chromatic symmetric function of graphs from Borcherds algebras
• A symmetric function generalization of the chromatic polynomial of a graph
• Graphs with equal chromatic symmetric functions
• The chromatic symmetric functions of trivially perfect graphs and cographs
• Chromatic symmetric functions of hypertrees
• Classes of graphs with \(e\)-positive chromatic symmetric function
• Chromatic quasisymmetric functions of directed graphs
• A note on Smarandachely consistent symmetric n-marked graph
• On the chromatic number of certain highly symmetric graphs

Cites work

• A deletion-contraction relation for the chromatic symmetric function
• A symmetric function generalization of the chromatic polynomial of a graph
• A vertex-weighted Tutte symmetric function, and constructing graphs with equal chromatic symmetric function
• A weighted graph polynomial from chromatic invariants of knots
• Chromatic bases for symmetric functions
• Chromatic quasisymmetric functions
• Extended chromatic symmetric functions and equality of ribbon Schur functions
• Graphs with equal chromatic symmetric functions
• scientific article; zbMATH DE number 1601795 (Why is no real title available?)
• scientific article; zbMATH DE number 1268810 (Why is no real title available?)
• scientific article; zbMATH DE number 1181673 (Why is no real title available?)
• Isomorphism of weighted trees and Stanley's isomorphism conjecture for caterpillars
• Lollipop and lariat symmetric functions
• Marked Graphs and the Chromatic Symmetric Function
• On an algorithm for comparing the chromatic symmetric functions of trees
• On distinguishing trees by their chromatic symmetric functions
• On Stanley's chromatic symmetric function and clawfree graphs
• On trees with the same restricted \(U\)-polynomial and the Prouhet-Tarry-Escott problem
• Proper caterpillars are distinguished by their chromatic symmetric function
• The connected partition lattice of a graph and the reconstruction conjecture
• The kernel of chromatic quasisymmetric functions on graphs and hypergraphic polytopes
• The Tutte-Potts connection in the presence of an external magnetic field

Cited in

(15)

• On Stanley's chromatic symmetric function and clawfree graphs
• Classes of graphs with \(e\)-positive chromatic symmetric function
• The connected partition lattice of a graph and the reconstruction conjecture
• Marked Graphs and the Chromatic Symmetric Function
• A rooted variant of Stanley's chromatic symmetric function
• A class of trees determined by their chromatic symmetric functions
• Proper q-caterpillars are distinguished by their chromatic symmetric functions
• Chromatic symmetric functions and polynomial invariants of trees
• Chromatic symmetric functions and change of basis
• The Kneser chromatic function distinguishes trees
• The chromatic symmetric function in the star-basis
• Chromatic MacMahon symmetric functions of graphs
• The chromatic symmetric function for unicyclic graphs
• On e-positivity of trees and connected partitions
• On the reconstruction of trees from their chromatic symmetric functions

This page was built for publication: Marked Graphs and the Chromatic Symmetric Function

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6046819)