Symmetric Chromatic Polynomial of Trees

Original · EN

In a 1995 paper Richard Stanley defined XG, the symmetric chromatic polynomial of a Graph G=(V,E). He then conjectured that XG distinguishes trees; a conjecture which still remains open. XG can be represented as a certain collection of integer partitions of |V| induced by each S E, which is very approachable with the aid of a computer. Our research involved writing a computer program for efficient verification of this conjecture for trees up to 23 vertices. In this process, we also gather trees with matching collections of integer partitions of a fixed number of parts. For each k=2, 3, 4, 5, we provide the smallest pair of trees whose partitions of k parts agree. In 2013, Orellana and Scott give a proof of a weaker version of Stanely's conjecture for trees with one centroid. We prove a similar result for arbitrary trees, and provide examples to show that this result, combined with that of Orellana and Scott, is optimal.