Spiders and their kin: an investigation of Stanley's chromatic symmetric function for spiders and related graphs

DOI10.1007/S00373-020-02230-4MaRDI QIDQ2657070zbMATH OpenOpenAlexFDO

Authors Angèle M. Foley, Joshua Kazdan, Larissa Kröll, Sofía Martínez Alberga, Oleksii Melnyk, Alexander Tenenbaum

Publication date 17 March 2021

Published in Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1812.03476

zbMATH Keywords

\(e\)-positivitychromatic symmetric functions

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Symmetric functions and generalizations (05E05)

Abstract: We study the chromatic symmetric functions of graph classes related to spiders, namely generalized spider graphs (line graphs of spiders), and what we call horseshoe crab graphs. We show that no two generalized spiders have the same chromatic symmetric function, thereby extending the work of Martin, Morin and Wagner. Additionally, we establish that a subclass of generalized spiders, which we call generalized nets, has no e-positive members, providing a more general counterexample to the necessity of the claw-free condition. We use yet another class of generalized spiders to construct a counterexample to a problem involving the $e$-positivity of claw-free, P4-sparse graphs, showing that Tsujie's result on the e-positivity of claw-free, P4-free graphs cannot be extended to graphs in this set. Finally, we investigate the e-positivity of another type of graphs, the horseshoe crab graphs (a class of unit interval graphs), and prove the positivity of all but one of the coefficients. This has close connections to the work of Gebhard and Sagan and Cho and Huh.

Recommendations

• The \(e\)-positivity and Schur positivity of some spiders and broom trees
• On the \(e\)-positivity of trees and spiders
• Resolving Stanley's \(e\)-positivity of claw-contractible-free graphs
• Chromatic symmetric functions and \(H\)-free graphs
• A few more trees the chromatic symmetric function can distinguish

Cites work

• A chromatic symmetric function in noncommuting variables
• A symmetric function generalization of the chromatic polynomial of a graph
• A tree representation for \(P_ 4\)-sparse graphs
• Chromatic quasisymmetric functions
• Graph colorings and related symmetric functions: ideas and applications: A description of results, interesting applications, and notable open problems.
• Graphs with equal chromatic symmetric functions
• scientific article; zbMATH DE number 1601795 (Why is no real title available?)
• scientific article; zbMATH DE number 428989 (Why is no real title available?)
• scientific article; zbMATH DE number 739282 (Why is no real title available?)
• Incomparability graphs of \((3+1)\)-free posets are \(s\)-positive
• Lollipop and lariat symmetric functions
• No starlike trees are cospectral
• On $e$-Positivity and $e$-Unimodality of Chromatic Quasi-symmetric Functions
• On distinguishing trees by their chromatic symmetric functions
• On extended P₄-reducible and extended P₄-sparse graphs
• On immanants of Jacobi-Trudi matrices and permutations with restricted position
• On variations of \(P_{4}\)-sparse graphs
• Recognizing P₄ -Sparse Graphs in Linear Time
• Resolving Stanley's \(e\)-positivity of claw-contractible-free graphs
• The chromatic symmetric functions of trivially perfect graphs and cographs
• The cohomology of abelian Hessenberg varieties and the Stanley-Stembridge conjecture
• Unit interval orders and the dot action on the cohomology of regular semisimple Hessenberg varieties

Cited in

(12)

• On the \(e\)-positivity of \((claw, 2K_2)\)-free graphs
• The twinning operation on graphs does not always preserve e-positivity
• The \(e\)-positivity and Schur positivity of some spiders and broom trees
• On the \(e\)-positivity of trees and spiders
• Chromatic symmetric functions in noncommuting variables revisited
• scientific article; zbMATH DE number 6277728 (Why is no real title available?)
• A rooted variant of Stanley's chromatic symmetric function
• Proper q-caterpillars are distinguished by their chromatic symmetric functions
• The e-positivity of some new classes of graphs
• The e-positivity of the chromatic symmetric function for twinned paths and cycles
• Schur-positivity for generalized nets
• Resolving Stanley's \(e\)-positivity of claw-contractible-free graphs

This page was built for publication: Spiders and their kin: an investigation of Stanley's chromatic symmetric function for spiders and related graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2657070)