On graphs with equal and different Kromatic symmetric functions
On graphs with equal and different Kromatic symmetric functions
The Kromatic symmetric function (KSF) $\overline{X}_G$ of a graph $G$ is a $K$-analogue introduced by Crew, Pechenik, and Spirkl in arXiv:2301.02177 of Stanley's chromatic symmetric function (CSF) $X_G$. The KSF is known to distinguish some pairs of graphs with the same CSF. The first author showed in arXiv:2403.15929 and arXiv:2502.21285 that the number of copies in $G$ of certain induced subgraphs can be determined given $\overline{X}_G$, and conjectured that $\overline{X}_G$ distinguishes all graphs. We disprove that conjecture by finding four pairs of 8-vertex graphs with equal KSF, as well as giving several ways to use existing graph pairs with equal KSF to construct larger graph pairs that also have equal KSF. On the other hand, we show that many of the graph pairs from the constructions of Orellana and Scott in arXiv:1308.6005 and of Aliste-Prieto, Crew, Spirkl, and Zamora in arXiv:2007.11042 of graphs with the same CSF are distinguished by the KSF, thus also giving some new examples of cases where the KSF is a stronger invariant than the CSF.
Laura Pierson、Soham Samanta
数学
Laura Pierson,Soham Samanta.On graphs with equal and different Kromatic symmetric functions[EB/OL].(2025-08-25)[2025-09-05].https://arxiv.org/abs/2508.17682.点此复制
评论