On an algorithm for comparing the chromatic symmetric functions of trees

MaRDI QIDQ5206924zbMATH OpenFDO

Authors Simon Heil, Caleb Ji

Publication date 19 December 2019

Full work available at URL https://arxiv.org/abs/1801.07363, http://ajc.maths.uq.edu.au/pdf/75/ajc_v75_p210.pdf

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)

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.

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

Cites work

• scientific article; zbMATH DE number 1268810 (Why is no real title available?)
• A symmetric function generalization of the chromatic polynomial of a graph
• Explicit Bounds for Some Functions of Prime Numbers
• Graphs with equal chromatic symmetric functions
• On distinguishing trees by their chromatic symmetric functions
• Proper caterpillars are distinguished by their chromatic symmetric function

Cited in

(24)

• Proper caterpillars are distinguished by their chromatic symmetric function
• A class of trees determined by their chromatic symmetric functions
• 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
• Schur and \(e\)-positivity of trees and cut vertices
• Homogeneous sets in graphs and a chromatic multisymmetric function
• 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
• Algorithms for solving the symmetry number problem on trees
• The chromatic symmetric function of a graph centred at a vertex
• A note on distinguishing trees with the chromatic symmetric function
• Quasisymmetric functions distinguishing trees
• 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

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)