Marked Graphs and the Chromatic Symmetric Function

DOI10.1137/22M148046XzbMATH Open1520.05051arXiv2202.11787MaRDI QIDQ6046819FDOQ6046819

Authors:

Publication date: 6 September 2023

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

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.

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

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

zbMATH Keywords

treeschromatic symmetric functionchromatic basis

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (8)

• Proper \(q\)-caterpillars are distinguished by their chromatic symmetric functions
• Marked Graphs and the Chromatic Symmetric Function
• On Stanley's chromatic symmetric function and clawfree graphs
• A rooted variant of Stanley's chromatic symmetric function
• Classes of graphs with \(e\)-positive chromatic symmetric function
• Chromatic symmetric functions and polynomial invariants of trees
• The connected partition lattice of a graph and the reconstruction conjecture
• A class of trees determined by 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)