The chromatic symmetric function of a graph centred at a vertex

Farid Aliniaeifard¹ ; Victor Wang² ; Stephanie van Willigenburg¹

¹University of British Columbia
²Harvard University

The electronic journal of combinatorics, Tome 31 (2024) no. 4

Résumé

We discover new linear relations between the chromatic symmetric functions of certain sequences of graphs and apply these relations to find new families of $e$-positive unit interval graphs. Motivated by the results of Gebhard and Sagan, we revisit their ideas and reinterpret their equivalence relation in terms of a new quotient algebra of NCSym. We investigate the projection of the chromatic symmetric function $Y_G$ in noncommuting variables in this quotient algebra, which defines $y_{G : v}$, the chromatic symmetric function of a graph $G$ centred at a vertex $v$. We then apply our methods to $y_{G : v}$ and find new families of unit interval graphs that are $(e)$-positive, a stronger condition than classical $e$-positivity, thus confirming new cases of the $(3+1)$-free conjecture of Stanley and Stembridge. In our study of $y_{G : v}$, we also describe methods of constructing new $e$-positive graphs from given $(e)$-positive graphs and classify the $(e)$-positivity of trees and cut vertices. We moreover construct a related quotient algebra of NCQSym to prove theorems relating the coefficients of $y_{G : v}$ to acyclic orientations of graphs, including a noncommutative refinement of Stanley's sink theorem.

Détail

DOI : 10.37236/12319

Classification : 05E05, 05A18, 05C15, 05C20, 05C25, 05C75
Mots-clés : deletion-contraction, symmetric function in noncommuting variables