\(H\)-chromatic symmetric functions (Q2121759)

The paper under review is motivated by Stanley's isomorphism conjecture, which states that non-isomorphic trees can be distinguished by their chromatic symmetric functions. This conjecture is still open though partial results have been obtained by several research groups. In this paper, the authors introduce the concept of \(H\)-chromatic symmetric functions and then study their uniqueness problems similar to Stanley's isomorphism conjecture. Given a graph \(H\) with \(n\) vertices and a graph \(G\) with \(k\) vertices \(v_1,\ldots,v_k\), the \(H\)-chromatic symmetric function of \(G\), denoted by \(X_G^H\), is defined by \[ X_G^H=\sum_{\phi}\sum_{\kappa}\prod_{i=1}^k x_{\kappa(v_i)}, \] where \(\phi\) ranges over all labelings of \(H\) with \(\{1,2,\ldots,n\}\) and \(\kappa\) ranges over all proper \((H,\phi)\)-colorings of \(G\). Given the above definition, it is natural to ask when \(X_{G_1}^H=X_{G_2}^H\) for fixed \(H\) and when \(X_{G}^{H_1}=X_{G}^{H_2}\) for fixed \(G\). The authors remark that for fixed \(H\) one can always find \(G_1\) and \(G_2\) such that \(X_{G_1}^H=X_{G_2}^H\). They also show that there always exists a graph \(H\) to distinguish given finitely many graphs by their \(H\)-chromatic symmetric functions. Most of the subsequent sections are devoted to the study of the properties of \(X_G^H\) when \(G\) or \(H\) is a complete bipartite graph. At the end of this paper, the authors also propose some problems and conjectures on \(H\)-chromatic symmetric functions. One of the most interesting conjectures is that for two non-isomorphic trees \(T_1\) and \(T_2\) there holds \(X_{T_1}^{T_1}\neq X_{T_2}^{T_2}\). It should be mentioned that this conjecture does not imply Stanley's isomorphism conjecture.