Counting induced subgraphs with the Kromatic symmetric function

Abstract

The chromatic symmetric function $X_G$ is a sum of monomials corresponding to proper vertex colorings of a graph $G$. Crew, Pechenik, and Spirkl (2023) recently introduced a $K$-theoretic analogue ${\overline{X}}_G$ called the Kromatic symmetric function, where each vertex is instead assigned a nonempty set of colors such that adjacent vertices have nonoverlapping color sets. $X_G$ does not distinguish all graphs, but a longstanding open question is whether it distinguishes all trees. We conjecture that ${\overline{X}}_G$ does distinguish all graphs. As evidence towards this conjecture, we show that ${\overline{X}}_G$ determines the number of copies in $G$ of certain induced subgraphs on 4 and 5 vertices as well as the number of induced subgraphs isomorphic to each graph consisting of a star plus some number of isolated vertices.

arXiv comment12 pages, comments welcome! v2: corrected a small error with one of the order 5 graphs