A few more trees the chromatic symmetric function can distinguish

DOI10.2140/INVOLVE.2020.13.109zbMATH Open1431.05041OpenAlexW3101089388MaRDI QIDQ2299412FDOQ2299412

Authors Jake Huryn, S. Chmutov

Publication date 21 February 2020

Published in Involve (Search for Journal in Brave)

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

zbMATH Keywords

combinatoricsgraph theorychromatic symmetric function

Mathematics Subject Classification ID

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

Abstract: A well-known open problem in graph theory asks whether Stanley's chromatic symmetric function, a generalization of the chromatic polynomial of a graph, distinguishes between any two non-isomorphic trees. Previous work has proven the conjecture for a class of trees called spiders. This paper generalizes the class of spiders to $n$-spiders, where normal spiders correspond to $n=1$, and verifies the conjecture for $n=2$.

Recommendations

• A note on distinguishing trees with the chromatic symmetric function
• On distinguishing trees by their chromatic symmetric functions
• Quasisymmetric functions distinguishing trees
• \(H\)-chromatic symmetric functions
• On an algorithm for comparing the chromatic symmetric functions of trees

Cites work

• scientific article; zbMATH DE number 714064 (Why is no real title available?)
• A symmetric function generalization of the chromatic polynomial of a graph
• A weighted graph polynomial from chromatic invariants of knots
• Isomorphism of weighted trees and Stanley's isomorphism conjecture for caterpillars
• On distinguishing trees by their chromatic symmetric functions

Cited in

(16)

• A note on distinguishing trees with the chromatic symmetric function
• Order quasisymmetric functions distinguish rooted trees
• The chromatic symmetric functions of trivially perfect graphs and cographs
• Proper caterpillars are distinguished by their chromatic symmetric function
• Coloring with a limited paintbox
• Quasysimmetric invariants for families of posets
• On an algorithm for comparing the chromatic symmetric functions of trees
• Proper \(q\)-caterpillars are distinguished by their chromatic symmetric functions
• 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 counterexample to a conjecture on Schur positivity of chromatic symmetric functions of trees
• 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

This page was built for publication: A few more trees the chromatic symmetric function can distinguish

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