Resolving Stanley's \(e\)-positivity of claw-contractible-free graphs (Q783748): Difference between revisions

Summary: In Stanley's seminal paper on the chromatic symmetric function [\textit{R. P. Stanley}, Adv. Math. 111, No. 1, 166--194 (1995; Zbl 0831.05027)], he stated that there was no known graph that was not contractible to the claw and whose chromatic symmetric function was not \(e\)-positive, that is, not a positive linear combination of elementary symmetric functions. We resolve this by giving infinite families of graphs that are not contractible to the claw and whose chromatic symmetric functions are not \(e\)-positive. Moreover, one such family is additionally claw-free, thus establishing that the \(e\)-positivity of chromatic symmetric functions is in general not dependent on the existence of an induced claw or of a contraction to a claw.