On an Algorithm for Comparing the Chromatic Symmetric Functions of Trees

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

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2018-02
Main Authors: Heil, Sam, Ji, Caleb
Format: Article
Language:English
Subjects:
Algorithms
Apexes
Trees (mathematics)
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:2331-8422