On an algorithm for comparing the chromatic symmetric functions of trees

zbMATH Open1434.05036arXiv1801.07363MaRDI QIDQ5206924FDOQ5206924

Authors: Simon Heil, Caleb Ji 

Publication date: 19 December 2019

Abstract: It is a long-standing question of Stanley whether or not the chromatic symmetric function (CSF) distinguishes unrooted trees. Previously, the best computational result, due to Russell, proved that it distinguishes all trees with at most $25$ vertices. In this paper, we present a novel probabilistic algorithm which may be used to check more efficiently that the CSF distinguishes a set of trees. Applying it, we verify that the CSF distinguishes all trees with up to $29$ vertices.

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

Recommendations

• A few more trees the chromatic symmetric function can distinguish
• On distinguishing trees by their chromatic symmetric functions
• A note on distinguishing trees with the chromatic symmetric function
• Quasisymmetric functions distinguishing trees
• Graphs with equal chromatic symmetric functions

zbMATH Keywords

chromatic symmetric functionunrooted tree

Mathematics Subject Classification ID

Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85) Symmetric functions and generalizations (05E05) Coloring of graphs and hypergraphs (05C15)

Cites Work

• Title not available (Why is that?)
• A symmetric function generalization of the chromatic polynomial of a graph
• On distinguishing trees by their chromatic symmetric functions
• Proper caterpillars are distinguished by their chromatic symmetric function
• Graphs with equal chromatic symmetric functions
• Explicit Bounds for Some Functions of Prime Numbers

Cited In (24)

• Proper caterpillars are distinguished by their chromatic symmetric function
• The \(e\)-positivity and Schur positivity of some spiders and broom trees
• On the \(e\)-positivity of trees and spiders
• A counterexample to a conjecture on Schur positivity of chromatic symmetric functions of trees
• Homogeneous sets in graphs and a chromatic multisymmetric function
• Schur and \(e\)-positivity of trees and cut vertices
• On the smallest trees with the same restricted \(U\)-polynomial and the rooted \(U\)-polynomial
• On distinguishing trees by their chromatic symmetric functions
• Marked Graphs and the Chromatic Symmetric Function
• A rooted variant of Stanley's chromatic symmetric function
• Extended chromatic symmetric functions and equality of ribbon Schur functions
• A vertex-weighted Tutte symmetric function, and constructing graphs with equal chromatic symmetric function
• The chromatic symmetric function of a graph centred at a vertex
• Algorithms for solving the symmetry number problem on trees
• 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
• Bijective proofs of proper coloring theorems
• Modular relations of the Tutte symmetric function
• A few more trees the chromatic symmetric function can distinguish
• A complete multipartite basis for the chromatic symmetric function
• Order quasisymmetric functions distinguish rooted trees
• A class of trees determined by their chromatic symmetric functions

This page was built for publication: On an algorithm for comparing the chromatic symmetric functions of trees

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