2022/02/23 by Aliste-Prieto, José, de Mier, Anna, Orellana, Rosa +1 · 1 citation
#05C60 #05E0 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2202.11787
The main result of this paper is the introduction of marked graphs and the marked graph polynomials (M-polynomial) associated with them. These polynomials can be defined via a deletion-contraction operation. These polynomials are a generalization of the W-polynomial introduced by Noble and Welsh and a specialization of the V-polynomial introduced by Ellis-Monaghan and Moffatt. In addition, we describe an important specialization of the M-polynomial which we call the D-polynomial. Furthermore, we give an efficient algorithm for computing the chromatic symmetric function of a graph in the star-basis of symmetric functions. As an application of these tools, we prove that proper trees of diameter at most 5 can be reconstructed from its chromatic symmetric function.