论文标题
标记图和色度对称函数
Marked graphs and the chromatic symmetric function
论文作者
论文摘要
本文的主要结果是引入标记图和与之相关的标记图多项式（$ M $ -Polynomial）。这些多项式可以通过删除 - 收集操作来定义。这些多项式是对Noble and Welsh引入的$ W $多项式的概括，也是Ellis-Monaghan和Moffatt引入的$ \ Mathbf {V} $ - 多项式的专业化。此外，我们描述了$ M $ - 多项式的重要专业化，我们称为$ d $ - 多种物质。此外，我们给出了一种有效的算法，用于计算对称函数的\ emph {star-basis}中图的色度对称函数。作为这些工具的应用，我们证明最多只能从其色度对称功能重建直径的正确树。
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 $\mathbf{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 \emph{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.
