Resolving Stanley's -positivity of claw-contractible-free graphs

  • Samantha Dahlberg

    Arizona State University, Tempe, USA
  • Angèle Foley

    Wilfrid Laurier University, Waterloo, Canada
  • Stephanie van Willigenburg

    University of British Columbia, Vancouver, Canada
Resolving Stanley's $e$-positivity of claw-contractible-free graphs cover

A subscription is required to access this article.

Abstract

In Stanley’s seminal 1995 paper on the chromatic symmetric function, he stated that there was no known graph that was not contractible to the claw and whose chromatic symmetric function was not -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 -positive. Moreover, one such family is additionally claw-free, thus establishing that the -positivity of chromatic symmetric functions is in general not dependent on the existence of an induced claw or of a contraction to a claw.

Cite this article

Samantha Dahlberg, Angèle Foley, Stephanie van Willigenburg, Resolving Stanley's -positivity of claw-contractible-free graphs. J. Eur. Math. Soc. 22 (2020), no. 8, pp. 2673–2696

DOI 10.4171/JEMS/974