A few more trees the chromatic symmetric function can distinguish

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

Authors: Jake Huryn, S. Chmutov 

Publication date: 21 February 2020

Published in: Involve (Search for Journal in Brave)

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$.

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

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

zbMATH Keywords

combinatoricsgraph theorychromatic symmetric function

Mathematics Subject Classification ID

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

Cites Work

• 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 distinguishing trees by their chromatic symmetric functions
• Title not available (Why is that?)

Cited In (16)

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

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)