Graphs with equal chromatic symmetric functions

DOI10.1016/J.DISC.2013.12.006MaRDI QIDQ394351zbMATH OpenOpenAlexFDO

Authors Geoffrey Scott, Rosa Orellana

Publication date 27 January 2014

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

treesgraph coloringunicyclic graphschromatic symmetric function

Mathematics Subject Classification ID

Trees (05C05) Symmetric functions and generalizations (05E05) Coloring of graphs and hypergraphs (05C15) Paths and cycles (05C38)

Abstract: Stanley [9] introduced the chromatic symmetric function $$ associated to a simple graph $G$ as a generalization of the chromatic polynomial of $G$. In this paper we present a novel technique to write $$ as a linear combination of chromatic symmetric functions of smaller graphs. We use this technique to give a sufficient condition for two graphs to have the same chromatic symmetric function. We then construct an infinite family of pairs of unicyclic graphs with the same chromatic symmetric function, answering the question posed by Martin, Morin, and Wagner [7] of whether such a pair exists. Finally, we approach the problem of whether it is possible to determine a tree from its chromatic symmetric function. Working towards an answer to this question, we give a classification theorem for single-centroid trees in terms of data closely related to its chromatic symmetric function.

Recommendations

• scientific article; zbMATH DE number 4087686
• The chromatic symmetric functions of trivially perfect graphs and cographs
• Chromatic symmetric functions and \(H\)-free graphs
• A symmetric function generalization of the chromatic polynomial of a graph
• Chromatic symmetric function of graphs from Borcherds algebras
• scientific article; zbMATH DE number 5073889
• Classes of graphs with \(e\)-positive chromatic symmetric function
• A vertex-weighted Tutte symmetric function, and constructing graphs with equal chromatic symmetric function
• scientific article; zbMATH DE number 4089574

Cites work

• scientific article; zbMATH DE number 1268810 (Why is no real title available?)
• scientific article; zbMATH DE number 2203240 (Why is no real title available?)
• scientific article; zbMATH DE number 3290993 (Why is no real title available?)
• A chromatic symmetric function in noncommuting variables
• A symmetric function generalization of the chromatic polynomial of a graph
• Graph theory
• On distinguishing trees by their chromatic symmetric functions

Cited in

(47)

• A note on distinguishing trees with the chromatic symmetric function
• Order quasisymmetric functions distinguish rooted trees
• Combinatorial Hopf algebras of simplicial complexes.
• Chromatic bases for symmetric functions
• An update on Haiman's conjectures
• The chromatic symmetric functions of trivially perfect graphs and cographs
• Chromatic symmetric functions from the modular law
• A vertex-weighted Tutte symmetric function, and constructing graphs with equal chromatic symmetric function
• The \(e\)-positivity of some new classes of graphs
• The connected partition lattice of a graph and the reconstruction conjecture
• The kernel of chromatic quasisymmetric functions on graphs and hypergraphic polytopes
• \(H\)-chromatic symmetric functions
• Extended chromatic symmetric functions and equality of ribbon Schur functions
• Isomorphism of weighted trees and Stanley's isomorphism conjecture for caterpillars
• All totally symmetric colored graphs
• Resolving Stanley's \(e\)-positivity of claw-contractible-free graphs
• The kernel of chromatic quasisymmetric functions on graphs and nestohedra
• On an algorithm for comparing the chromatic symmetric functions of trees
• The twinning operation on graphs does not always preserve \(e\)-positivity
• A rooted variant of Stanley's chromatic symmetric function
• On distinguishing trees by their chromatic symmetric functions
• Chromatic symmetric functions and polynomial invariants of trees
• Quasisymmetric functions distinguishing trees
• A categorification of the chromatic symmetric function
• Lollipop and lariat symmetric functions
• Chromatic symmetric functions in noncommuting variables revisited
• Recovering a tree from the lengths of subtrees spanned by a randomly chosen sequence of leaves
• The chromatic symmetric function of a graph centred at a vertex
• A deletion-contraction relation for the chromatic symmetric function
• The \(e\)-positivity of two classes of cycle-chord graphs
• The amazing chromatic polynomial
• Marked Graphs and the Chromatic Symmetric Function
• Classes of graphs with \(e\)-positive chromatic symmetric function
• Melting lollipop chromatic quasisymmetric functions and Schur expansion of unicellular LLT polynomials
• The \(e\)-positivity and Schur positivity of some spiders and broom trees
• Homogeneous sets in graphs and a chromatic multisymmetric function
• Bijective proofs of proper coloring theorems
• Modular relations of the Tutte symmetric function
• Schur and \(e\)-positivity of trees and cut vertices
• On trees with the same restricted \(U\)-polynomial and the Prouhet-Tarry-Escott problem
• On the strength of chromatic symmetric homology for graphs
• A large class of conjecturally stable chromatic symmetric functions
• A class of trees determined by their chromatic symmetric functions
• Spiders and their kin: an investigation of Stanley's chromatic symmetric function for spiders and related graphs
• On the \(e\)-positivity of trees and spiders
• A complete multipartite basis for the chromatic symmetric function
• Chromatic posets

Describes a project that uses

Uses Software

• GitHub

This page was built for publication: Graphs with equal chromatic symmetric functions

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