Back to Search
Start Over
Resolving Stanley's $e$-positivity of claw-contractible-free graphs
- Publication Year :
- 2017
-
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 $e$-positive, namely, 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.<br />Comment: Label corrected in Example 3.1, 28 pages, final version to appear in J. Eur. Math. Soc. (JEMS)
Details
- Database :
- arXiv
- Publication Type :
- Report
- Accession number :
- edsarx.1703.05770
- Document Type :
- Working Paper