Counting induced subgraphs with the Kromatic symmetric function

2024/03/23 by Laura Pierson, Pierson, Laura · 1 citation
Computer Science · Mathematics · #Graph Theory and Algorithms #Graph theory and applications #Data Management and Algorithms

paper · pdf · doi:10.48550/arxiv.2403.15929

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 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 X_G does distinguish all graphs. As evidence towards this conjecture, we show that 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.

Cited by

• On graphs with equal and different Kromatic symmetric functions

Related

• On graphs with equal and different Kromatic symmetric functions
• Graphs with Equal Chromatic Symmetric Functions
• A class of trees determined by their chromatic symmetric functions
• Distinguishability and linear independence for H-chromatic symmetric functions
• On distinguishing special trees by their chromatic symmetric functions