A Schur-positivity classification for complete multipartite graphs

Abstract

A graph is Schur-positive if its chromatic symmetric function expands non-negatively in the Schur basis. We determine a full Schur-positivity classification for complete multipartite graphs by showing that a complete multipartite graph $K_{\hat{I}}»$ is Schur-positive if and only if either $\hat{I}{»}_i\in \{1,2\}$ for all $i$ or $\hat{I}»=(3,2^2)$ for some ${\hat{I}}^2\ge 1$. These results extend earlier classifications for complete bipartite and complete tripartite graphs to full generality. Our proofs combine structural arguments ruling out most cases, with a combinatorial analysis of Schur coefficients for the remaining family $K_{(3,2^2)}$ via special rim hook $G$-tabloids. Along the way, we establish a simpler formula for Schur coefficients of incomparability graphs, which we then apply to compute the coefficients of interest in terms of non-increasing sequences.

16 pages