A Complete Multipartite Basis for the Chromatic Symmetric Function

Abstract

In the vector space of symmetric functions, the elements of the basis of elementary symmetric functions are (up to a factor) the chromatic symmetric functions of disjoint unions of cliques. We consider their graph complements, the functions {rλ:λ an integer partition} defined as chromatic symmetric functions of complete multipartite graphs. This basis was first introduced by Penaguiao [J. Combin. Theory Ser. A, 175 (2020), 105258]. We provide a combinatorial interpretation for the coefficients of the change-of-basis formula between the rλ and the monomial symmetric functions, and we show that the coefficients of the chromatic and Tutte symmetric functions of a graph G when expanded in the r-basis enumerate certain intersections of partitions of V(G).