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) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Symmetric functions and generalizations (05E05)

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

• 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
• scientific article; zbMATH DE number 1268810 (Why is no real title available?)
• On distinguishing trees by their chromatic symmetric functions
• Proper caterpillars are distinguished by their chromatic symmetric function

Cited in

(29)

• Order quasisymmetric functions distinguish rooted trees
• Extended chromatic symmetric functions and equality of ribbon Schur functions
• Modular relations of the Tutte 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
• On the smallest trees with the same restricted U-polynomial and the rooted U-polynomial
• Schur and \(e\)-positivity of trees and cut vertices
• A few more trees the chromatic symmetric function can distinguish
• Algorithms for solving the symmetry number problem on trees
• On distinguishing trees by their chromatic symmetric functions
• A vertex-weighted Tutte symmetric function, and constructing graphs with equal chromatic symmetric function
• A note on distinguishing trees with the chromatic symmetric function
• Proper caterpillars are distinguished by their chromatic symmetric function
• Bijective proofs of proper coloring theorems
• A complete multipartite basis for the chromatic symmetric function
• Marked Graphs and the Chromatic Symmetric Function
• Quasisymmetric functions distinguishing trees
• A rooted variant of Stanley's chromatic symmetric function
• A class of trees determined by their chromatic symmetric functions
• Homogeneous sets in graphs and a chromatic multisymmetric function
• The chromatic symmetric function of a graph centred at a vertex
• Quasysimmetric invariants for families of posets
• Chromatic symmetric functions and polynomial invariants of trees
• The Kneser chromatic function distinguishes trees
• The chromatic symmetric function in the star-basis
• Schur-positivity for generalized nets
• On graphs with equal and different Kromatic symmetric functions
• Title not available (Why is no real title available?)

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)